{"id":"dccc1f42-6cef-44be-b01a-b66078f632d4","arxiv_id":"2603.17489","paper_version":4,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.5,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"FFPTAS approximates the amortized multi-copy optimum and forms a complexity class strictly between P and FPTAS for fractionally-polynomial problems (assuming P ≠ NP).","lead":"The paper defines FFPTAS, an approximation scheme that targets an amortized (multi-copy) optimum rather than the ordinary optimum. It sits strictly between polynomial-time solvability and classical FPTAS for a natural class of optimization problems (assuming P ≠ NP).","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The Reader correctly isolates the FracP restriction as the weakest modelling assumption and notes that the paper itself supplies the counter-example (Appendix A) showing why the restriction cannot be dropped. All four directions of Theorem 6 rest on elementary, checkable arguments rather than on unproved lemmas or external black boxes. The only place a subtle counting error could hide is Claim 8 inside the hardness proof for 4-partition; that claim is short, purely combinatorial, and can be verified by hand for a concrete small m. Because that verification is expected to succeed, and because every other step is either a standard FPTAS invocation or a direct comparison of bit lengths, the sandwich stands. No adjustment to the ACCEPT verdict is warranted.","tokens_in":20361,"tokens_out":482,"duration_ms":5287,"concrete_test":"Independently re-derive the cardinality argument of Claim 8 (the only non-routine combinatorial step in part (4)): given a 4-partition of X4 with every bin sum ≥ (4m+2)S, verify that some two bins must contain exactly the 2(m+1) small items of size 4S and that the remaining two bins therefore form an equal-cardinality equal-sum partition of X2. If the counting fails for some integer m, the hardness reduction collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central sandwich of Theorem 6 is proved inside FracP by four explicit, self-contained arguments: (1) trivial reduction from exact OptInt, (2) FFPTAS for 2-partition via an FPTAS for the critical-coordinate variant, (3) iterative FFPTAS calls that recover an FPTAS once the bit-length of OptInt/OptFrac is polynomial, and (4) reduction from Equal-Cardinality Partition that shows 4-partition has no FFPTAS. Appendix A correctly shows why the FracP restriction is necessary (P is not contained in unrestricted FFPTAS). The constructions are fully explicit, the definitions are consistent, and the only acknowledged limitation (the artificial union that defines class C) is already stated by the authors. No hidden assumption, circularity, or gap in the four parts appears to threaten the claim.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper introduces FFPTAS, an approximation notion for optimization problems based on an amortized (replication) relaxation OptFrac(x) := sup_k OptInt(x^{*k})/k. An FFPTAS returns a value v with (1-t)·OptFrac(x) ≤ v ≤ OptInt(x) (or None) in time poly(len(x),1/t). Restricting to fractionally-polynomial problems FracP (OptFrac poly-time computable and OptInt poly-space representable), Theorem 6 proves the sandwich (P ∩ FracP) ⊊ (FFPTAS ∩ FracP) ⊊ (FPTAS ∩ FracP) assuming P ≠ NP: (1) poly-time exact algorithms yield FFPTAS; (2) max-min 2-partition has an FFPTAS (via FPTAS for a critical-coordinate variant) but is NP-hard; (3) FFPTAS implies FPTAS by polynomially many iterative calls that exploit poly bit-length; (4) 4-way partition has an FPTAS but no FFPTAS (reduction from Equal-Cardinality Partition). Appendices show the FracP restriction is necessary and develop a graph-theoretic example (Restricted Shortest Path) with an NP-hard special case that admits FFPTAS.","tokens_in":20581,"tokens_out":1115,"duration_ms":9732,"significance":"If correct, the work cleanly inserts a new intermediate class between P and FPTAS for optimization problems, refining the classical hierarchy of approximation schemes. The four directions of Theorem 6 are proved by explicit algorithmic constructions and classical NP-hardness reductions rather than asymptotic or conditional arguments; the definitions are self-contained and the necessity of the FracP restriction is demonstrated by a concrete counter-example (Appendix A). The amortized relaxation is natural (analogous to fractional chromatic number / Shannon capacity) and the paper supplies both maximization and minimization instantiations, including a non-trivial graph problem (EERSP) that is still NP-hard yet admits FFPTAS. These are genuine contributions to the structural theory of approximation algorithms.","major_comments":[{"comment":"The abstract and the opening of §4 claim a new class that is a strict superset of P and a strict subset of FPTAS. Theorem 6 establishes the sandwich only inside FracP; outside FracP, Appendix A (Propositions 10–11) shows P ⊈ FFPTAS. The authors later define the artificial union C := P ∪ (FFPTAS ∩ FracP) to recover P ⊊ C ⊊ FPTAS. The abstract should be aligned with this precise statement (or the definition of C should be moved earlier) so that the headline claim matches the theorems that are actually proved.","section":null},{"comment":"§3.4, Claim 8 and the surrounding reduction: the argument that some pair of bins must contain exactly 2(m+1) items relies on a short case analysis of pair-sums. The write-up is correct but dense; a one-line verification that the three pairings force a contradiction when all pair-sums are ≤ 2m+1 would make the load-bearing combinatorial step easier to check. This is not a correctness gap, but it is the only non-routine step in the hardness direction and should be fully transparent.","section":null}],"minor_comments":[{"comment":"Definition 3 (FFPTAS): the parenthetical “if such a value exists” is clear, but an explicit note that the algorithm may return None even when OptInt is positive would prevent misreading by readers used to classical FPTAS.","section":null},{"comment":"Algorithm 3 (FPTAS from FFPTAS): the bound k ≤ q(len(x))/ε uses log(1/(1-ε)) > ε; a short remark that a tighter series expansion is unnecessary for the polynomial bound would be helpful.","section":null},{"comment":"Appendix B, Open Question 1: the question whether full RSP admits an FFPTAS is well-motivated; a one-sentence pointer to the obstacle (lack of a uniform additive-gap bound of the kind used for EERSP) would orient future work.","section":null},{"comment":"Typographical: “P̸=NP” appears both with and without spaces; unify. The arXiv identifier in the header is 2603.17489v4 — confirm final version number before camera-ready.","section":null},{"comment":"References: Woeginger’s FPTAS survey [17] and the classical Partition hardness [4] are correctly cited; a pointer to the modern treatment of fractional graph parameters (e.g., Scheinerman–Ullman) already present could be moved earlier for readers less familiar with amortized relaxations.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is technically solid and the sandwich result is new. The only presentational risk is that the abstract over-states the unrestricted claim; once that is tightened the paper is ready for a theory journal. Scope is appropriate for a complexity / approximation venue."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The one thing to know: they define FFPTAS by approximating the amortized multi-copy optimum OptFrac (sup of OptInt(x*k)/k) instead of OptInt, and prove that inside fractionally-polynomial problems this sits strictly between P and FPTAS under P≠NP.\n\nWhat is new is the formalization and the sandwich. OptFrac is the natural multi-copy amortization (same spirit as fractional chromatic number or Shannon capacity). They turn it into a fully poly-time scheme and give four explicit directions: exact OptInt yields FFPTAS; 2-partition has FFPTAS (via an FPTAS for a critical-coordinate Subset-Sum variant) but is NP-hard; FFPTAS yields FPTAS by a polynomial number of calls that exploit poly bit-length of OptInt/OptFrac; 4-partition has FPTAS but no FFPTAS by reduction from Equal-Cardinality Partition. Appendix B adds a graph example (expensive-edge RSP) that is still NP-hard and has an FFPTAS. Constructions are fully explicit; no fitted parameters, no circularity.\n\nThey do the bookkeeping honestly. Definition 5 (FracP: OptFrac in P and OptInt poly-space) is necessary—Appendix A builds a poly-time OptInt whose OptFrac encodes SAT, so unrestricted P is not inside FFPTAS. They fix the hierarchy with the artificial union C = P ∪ (FFPTAS ∩ FracP). The abstract’s “strict superset of P and subset of FPTAS” is slightly loose until you read that fix; the body is careful.\n\nSoft spots are proportional, not load-bearing. FracP is a real restriction, not a free lunch. Class C is a bit ad hoc. The general Restricted Shortest Path question is left open. None of that breaks the four parts of Theorem 6.\n\nThis is for people who care about the fine structure of approximation schemes and intermediate classes. Math and citations look solid (Woeginger, classical partition hardness, fractional graph theory). I would send it to a serious referee and would bring it to reading group. Worth engaging if you work on FPTAS or combinatorial optimization.","headline":"Clean intermediate class between P and FPTAS via amortized multi-copy optima, with matching partition examples; the sandwich is real inside FracP and carefully proved.","tokens_in":21172,"tokens_out":554,"would_cite":true,"duration_ms":10716,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","90C27","68W25"],"pacs":[],"model":"grok-4.5","headline":"An amortized relaxation yields a new approximation class strictly between P and FPTAS.","keywords":["FPTAS","FFPTAS","amortized optimum","approximation schemes","complexity classes","partition problems","fractional relaxation"],"falsifier":"Exhibit a fractionally-polynomial problem that has a classical FPTAS but also an FFPTAS while remaining NP-hard, or prove that every fractionally-polynomial problem with an FPTAS automatically has an FFPTAS (collapsing the strict separation claimed for 4-way partition).","tokens_in":21268,"feed_emoji":"📐","tokens_out":656,"duration_ms":7097,"temperature":0.7,"pith_summary":"The paper defines a new kind of approximation for hard optimization problems: instead of approximating the ordinary optimum, an algorithm approximates the amortized optimum—the best per-copy value you can get by solving many identical copies of the input together. That amortized value is always at least as large as the true optimum and acts like a fractional relaxation. The authors show that, for a natural class of problems where this amortized value is easy to compute and the true optimum is not too large to write down, every problem that can be solved exactly in polynomial time has such an approximation scheme, every problem that has one also has a classical FPTAS, and—assuming P is not equal to NP—there are problems that sit strictly in between. The result carves out a new complexity class for optimization that refines the usual hierarchy between exact polynomial-time algorithms and fully polynomial approximation schemes.","feed_headline":"New approximation class sits strictly between P and FPTAS","feed_subtitle":"Amortized multi-copy optima define a scheme stronger than FPTAS yet weaker than exact poly-time algorithms","key_machinery":"The amortized (relaxed) optimum OptFrac(x) := sup_k OptInt(x^{*k})/k, the largest per-copy value attainable when k identical copies of the input are solved jointly; an FFPTAS approximates this value within factor (1−t) in time polynomial in the input size and 1/t, or correctly reports that no integral solution reaches that threshold.","core_discovery":"Assuming P ≠ NP, among fractionally-polynomial maximization problems the new FFPTAS notion sits strictly between polynomial-time solvability and classical FPTAS: every poly-time problem has an FFPTAS, every problem with an FFPTAS has an FPTAS, yet there exist problems with an FFPTAS but no poly-time algorithm and problems with an FPTAS but no FFPTAS.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Amortized multi-copy optima place FFPTAS strictly between P and FPTAS","FFPTAS sits strictly between polynomial time and classical FPTAS","New amortized approximation notion lies between P and FPTAS","FFPTAS is stronger than FPTAS yet weaker than exact poly-time algorithms","Amortized relaxation defines class strictly between P and FPTAS"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"The sandwich between P and FPTAS holds only for problems whose amortized optimum can be computed in polynomial time and whose true optimum can be written down in polynomial space; without that restriction the inclusions already fail.","fun_headline_variants_meta":{"raw":{"variants":["Amortized multi-copy optima place FFPTAS strictly between P and FPTAS","FFPTAS sits strictly between polynomial time and classical FPTAS","New amortized approximation notion lies between P and FPTAS","FFPTAS is stronger than FPTAS yet weaker than exact poly-time algorithms","Amortized relaxation defines class strictly between P and FPTAS"]},"model":"grok-4.5","effort":"low","cost_usd":0.005546,"raw_usage":{"total_tokens":1413,"prompt_tokens":637,"num_sources_used":0,"completion_tokens":100,"cost_in_usd_ticks":55460000,"prompt_tokens_details":{"text_tokens":637,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":676,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":637,"tokens_out":100,"duration_ms":5386,"temperature":1.0,"reasoning_tokens":676,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-13T23:07:39.786140+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Exhibit a fractionally-polynomial problem that has a classical FPTAS but also an FFPTAS while remaining NP-hard, or prove that every fractionally-polynomial problem with an FPTAS automatically has an FFPTAS (collapsing the strict separation claimed for 4-way partition).","supporting_citations":[],"review_version":2}