The landscape of computational hardness for optimization problems has three familiar landmarks. Polynomial-time solvability: the problem is easy. FPTAS (fully polynomial-time approximation scheme): the optimum is NP-hard to find exactly, but you can get within any desired multiplicative factor in polynomial time. NP-hardness without FPTAS: even good approximations are hard.
Between the first two landmarks, there is an invisible territory.
The paper identifies a natural approximation notion — applicable to NP-hard problems with binary-valued objective functions — that is provably strictly stronger than FPTAS but strictly weaker than polynomial-time exact solvability (assuming P ≠ NP). Problems in this class can be approximated better than any FPTAS achieves, but still cannot be solved exactly. The gap between “arbitrarily good approximation” and “exact solution” contains structure.
This is counterintuitive because FPTAS already provides arbitrarily small error. What could be “better” than arbitrarily close? The answer lies in the resource scaling: FPTAS runtime grows as a polynomial in 1/ε, where ε is the desired accuracy. The new class achieves a stronger guarantee — specific structural properties of the solution, not just closeness to optimal — that FPTAS cannot provide even with ε → 0.
The result means the boundary between tractable and intractable is not a wall but a gradient with finer grain than the standard complexity hierarchy reveals. Between “we can solve this” and “we can approximate this to any accuracy,” there exist problems that we can do something in between — better than approximate but not quite solve. The landscape of almost-solvability has more terrain than the map showed.
Complexity boundaries are not binary. They are layered, and the layers between the known landmarks contain natural problems that previous frameworks couldn't see.