The landscape between P and NP has finer structure than the binary dichotomy suggests. For NP-hard optimization problems, the question isn’t just “can you solve it exactly?” but “how well can you approximate it, and how fast?” An FPTAS (fully polynomial-time approximation scheme) finds a (1+ε)-approximate solution in time polynomial in both the input size and 1/ε. It’s the gold standard for approximation — as close to exact as you want, in polynomial time.

For optimization problems whose objective function takes only values 0 and 1, a new approximation notion sits strictly between FPTAS and exact polynomial-time computation. The notion exploits the binary structure: a (1+ε)-approximation to a 0-1 function is either exact (if the optimum is 1) or trivially satisfied (if the optimum is 0 and you return anything non-negative). The approximation only matters when distinguishing 0 from 1, and the new notion captures problems where this distinction can be made with additional structure that generic FPTAS doesn’t provide.

The separation is conditional on P ≠ NP. If P = NP, everything collapses — all three notions (P, the new notion, FPTAS) become the same. Under the standard assumption, the hierarchy is strict: there exist problems solvable by the new notion but not in P, and problems with FPTAS but not solvable by the new notion.

The result maps a previously invisible layer of approximation complexity. Between “exactly solvable” and “approximately solvable to any desired precision” lies a notion that captures problems where the binary structure of the objective provides leverage that generic approximation cannot.

The gap exists because 0-1 optimization has more structure than general optimization. The structure doesn’t make the problem easy. It makes it a different kind of hard.