An approximation notion between P and FPTAS

Erel Segal-Halevi; Samuel Bismuth

An approximation notion between P and FPTAS

T0 review · 2 major / 5 minor · reviewed 2026-07-13 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read An amortized relaxation yields a new approximation class strictly between P and FPTAS.

desk verdict 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. read the letter →

arxiv 2603.17489 v5 pith:ICIMLZ2D submitted 2026-03-18 cs.CC

Samuel Bismuth , Erel Segal-Halevi This is my paper · ORCID

classification cs.CC MSC 68Q2590C2768W25

keywords FPTASFFPTASamortizedoptimumapproximationschemescomplexityclassespartitionproblemsfractionalrelaxation

topics P versus NP

open problems P versus NP

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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).

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

What 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.

They 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.

Soft 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.

This 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.

Referee Report

2 major / 5 minor

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.

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 (2)

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.
§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.

minor comments (5)

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.
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.
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.
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.
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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: Theorem 6 is proved by explicit algorithms and classical NP-hardness reductions, not by self-definition or fitted inputs.

full rationale

The paper is a pure complexity-theory construction. OptFrac is defined from OptInt via replication (Definition 2); FFPTAS and FracP are defined from that (Definitions 3, 5). Parts (1)–(4) of Theorem 6 are proved by direct algorithms (Algorithm 1–3) and reductions from Equal-Cardinality Partition / Partition / SAT (classical, external). Appendix A constructs a counter-example showing why FracP is needed; Appendix B encodes RSP so that OptFrac equals the path LP and builds an FFPTAS for the EERSP special case. No parameter is fitted to data and then re-predicted; no uniqueness theorem is imported from the authors’ prior work as a load-bearing premise; the single self-citation [1] is motivational only. The sandwich (P ∩ FracP) ⊊ (FFPTAS ∩ FracP) ⊊ (FPTAS ∩ FracP) therefore stands or falls on the explicit constructions and classical hardness, not on circular reduction to its own inputs.

Assumptions & free parameters 0 free parameters · 4 assumptions · 3 invented entities

The work rests on standard complexity-theoretic background (P ≠ NP, classical NP-hardness of Partition variants, existence of FPTAS for certain DP-formulated problems via Woeginger’s scheme) together with the authors’ own definitions of amortized optimum and fractionally-polynomial problems. No free parameters are fitted; the only invented entities are the new algorithmic notion and the auxiliary class FracP.

assumptions (4)

domain assumption P ≠ NP
Used throughout Theorem 6 (parts 2 and 4) and the subsequent class separations; standard unproved assumption of complexity theory.
standard math Equal-Cardinality Partition is NP-hard
Cited from Garey & Johnson; used as the source problem in the reduction of part (4).
standard math Woeginger’s scheme yields an FPTAS for the critical-coordinate 2-partition variant and for k-way partition
Invoked in the constructions of Algorithms 2 and the FPTAS for P4; the scheme is a published black-box result.
domain assumption OptFrac is finite for every input under consideration
Stated explicitly after Definition 2; required for the approximation guarantees to be well-defined.

invented entities (3)

FFPTAS (Fractional Fully Polynomial Time Approximation Scheme)
purpose: New algorithmic notion that approximates the amortized multi-copy optimum rather than the ordinary optimum.
Defined in Definition 3; the entire paper is devoted to establishing its place in the complexity hierarchy.
Fractionally-polynomial problems (FracP)
purpose: Restricts attention to problems for which OptFrac is poly-time computable and OptInt has polynomial bit length, making the sandwich theorems hold cleanly.
Definition 5; without it the inclusion P ⊆ FFPTAS already fails (Appendix A).
Amortized / relaxed optimum OptFrac independent evidence
purpose: Supremum (or infimum) of the per-copy optimum over k-fold replications; plays the role of a fractional relaxation.
Definition 2; analogous to fractional graph parameters but newly applied to approximation schemes.

how reviews work

0 comments

Cite this review

Pith. "Pith review of An approximation notion between P and FPTAS." pith.science (2026). https://pith.science/paper/ICIMLZ2D

@misc{pith2026260317489,
  author       = {Pith},
  title        = {Pith review of: An approximation notion between P and FPTAS},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ICIMLZ2D}},
  note         = {Machine review of arXiv:2603.17489}
}

read the original abstract

We present an approximation notion for NP-hard optimization problems. The notion is based on an amortized relaxation: the relaxed optimum of an input is the largest per-copy value attainable when many copies of the input are solved together. Assuming P != NP, we prove that the new notion is strictly stronger than FPTAS, but strictly weaker than having a polynomial-time algorithm. Our results therefore reveal a new computational complexity class, which is a strict superset of P and a strict subset of FPTAS.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Pith tools

Reviewed July 13, 2026 · model on record in the stance chip above.