The Gap Between Polynomial Time And Np: An Infinite Ladder Of Complexity
Exploring the Gap Between Polynomial Time and NP-Completeness
The classes P and NP represent fundamental measures of computational complexity. P consists of all decision problems that can be solved in polynomial time by a deterministic Turing machine. NP consists of all decision problems where a “yes” answer can be verified in polynomial time given the right information or “certificate”. NP contains all problems in P, but it remains a major open question in computer science whether P actually equals NP.
There is strong evidence that P does not equal NP. Thousands of natural computational problems like the traveling salesman problem and integer factoring have been shown to be NP-complete, meaning they are the hardest problems in NP. If any NP-complete problem can be solved in polynomial time, then P = NP. But no polynomial-time algorithm has ever been found for any NP-complete problem despite decades of research.
The suspected gap between polynomial time and NP-complete intractability has led computer scientists to explore the complexity landscape between P and NP. This frontier resembles an infinite ladder of complexity classes, denoting problems with different constraints on resources like time, memory, randomness, and interaction. Studying the relationships between these classes provides deep insights into the fundamental barriers faced by algorithms. The structure of this ladder also guides researchers toward approaches that may resolve questions like P vs NP.
The Complexity Classes Between P and NP-Complete
Many complexity classes occupying the gap between P and NP have natural definitions. NP-intermediate problems have complexity strictly between polynomial time and NP-complete. The polynomial hierarchy PH models problems that can be solved by polynomial-time algorithms with increasing access to nondeterminism. #P contains counting and enumeration problems associated with decision problems in NP. NL models problems solvable in logarithmic memory space. BPP consists of problems with efficient probabilistic algorithms.
Results have shown similarities and differences between some of these classes. For example, the question NL = P would imply deterministic and non-deterministic logarithmic space are equivalent in power. But most classes in this intermediate region remain mysterious — it is not known if problems complete for various classes actually exist, or how these classes relate to each other or to P and NP.
Sparse Sets and Relativization
Early attempts to resolve P vs NP met obstacles from the technique of relativization. Complexity results are relativized when they are shown to hold relative to certain oracles, which are imaginary black boxes that algorithms can query to instantly solve specific problems. Baker, Gill, and Solovay demonstrated both worlds where P = NP and worlds where P ≠ NP can occur under relativization. This suggested that techniques relying on relativization cannot answer P vs NP.
Relativization ended up tightly connected to sparse sets — sets of integers with asymptotic density 0. Sparse sets exist in complexity classes like P and NP with rich and irregular structure. For many pairs of complexity classes X and Y, there are relativized worlds separating X from Y based on sparse sets. This implies P vs NP cannot be resolved via sparse sets. So proving P ≠ NP likely requires non-relativizing techniques that exploit the global structure of complexity classes.
Space-Bounded Complexity Classes
While time measures computational steps, space measures writable memory used by an algorithm. Complexity classes like L, NL, and PSPACE formalize problems solvable by algorithms using different space bounds. L requires logarithmic space, NL nondeterministic logarithmic space, and PSPACE polynomial space. Space-bounded classes connect closely to time — for instance, NL likely equals deterministic log space, and PSPACE contains all polynomial time problems.
Space classes highlight the knowledge versus search distinction in computation — the ability to verify a solution’s correctness given unlimited time does not imply the ability to find that solution. This manifests in containments like NP in PSPACE. Exploring space-bounded classes offers insight about knowledge, difficulty of search problems, and relationships between space and time bounds.
Alternation and the Polynomial Hierarchy
The polynomial hierarchy PH generalizes NP using alternation — informally, switching between existential and universal nondeterminism. The first level of PH is NP itself, expressing existential nondeterminism. The second level ΠP2 expresses universal then existential nondeterminism. Higher levels like ΣP3 and ΠP4 indicate more alternations.
PH measures this notion of limited nondeterminism. Results establish that problems become strictly harder at each new level of alternation. Relating PH to other classes like PSPACE informs the question of how much increasing nondeterminism enhances computation. Some bounds on PH also follow from circuit complexity lower bounds. Understanding the structure of PH may uncover insights about the source of intractability for hard problems.
Probabilistic Complexity Classes
Probabilistic complexity classes like BPP and RP capture efficient computation that can make random choices and have a small probability of error. Probabilistic algorithms cannot exceed mathematical limits on computation, but randomness allows simplicity and speedup. For example, BPP problems have fast solutions if you allow coin flips, while RP requires only one-sided error.
Connections exist between deterministic, nondeterministic, and probabilistic classes. Derandomization of BPP implies P = BPP, and relativizations imply BPP equals the PH. However their deterministic equivalents P and PH are suspected to differ, so resolving these containments could have major complexity implications. Studying probabilistic classes also enables sampling algorithms and cryptography with applications to learning and security.
Interactive Proofs and IP
Interactive proofs expand complexity classes to two-party communication complexity. An interactive verifier sends and receives messages with a powerful prover. IP consists of languages that have interactive proof systems with efficient verifiers. PS PACE generalizes IP by allowing polynomial-space verifiers.
Interactive protocols force concessions from entities who know solutions — the prover cannot compute everything alone, while the verifier cannot verify efficiently alone. IP equals PSPACE, suggesting optimal interactors together can match total computational power. Interactive complexity offers insights about knowledge, cooperation, and verification that impact cryptography, multi-agent systems, and models of human problem solving.
Quantum Complexity Classes
Quantum computing allows superposition and entanglement for algorithms with no equivalent classical behavior. Complexity classes like BQP and QMA model efficient quantum computation with bounds on error probability. Problematic containments like NP in BQP reflect suspected quantum advantages over classical schemes.
But despite demonstrated quantum speedups for specific problems, unconditionally proving gaps between quantum and classical classes remains challenging. Relativizations do not seem to separate quantum from classical classes. Quantum advantages may also come from subtle structural differences versus large complexity gaps. Further understanding quantum effects on space and time hierarchies could profoundly reshape algorithmic frontiers.
Where Hardness May Lie
Hardness stemming from NP-completeness or other sources prevents efficient solutions for many important problems. Exact algorithms take exponential time, while approximation schemes trade accuracy for efficiency. Hardness also connects to other concepts like information theory, cryptography, and circuit complexity lower bounds.
There are multiple viable hypotheses on origins of computational intractability. Sparse sets create relativized barriers, while the unique structure of the standard number line may enable complexity gaps. Space-time tradeoffs bound computation from two directions. Interaction permits verification of solutions found via different means. And stochasticity and quantum effects open additional computational modes outside standard models.
Current Research Directions
Many avenues exist towards understanding hardness and relationships between complexity classes. Algorithmic proof search leverages automated reasoning to elucidate hardness hypotheses. Resource tradeoffs explore links between time, space, randomness, and interaction. Mathematical approaches like algebraic geometry, analytic number theory, and Diophantine approximation connect complexity to wider mathematical settings. New computational models expand the problem solving landscape.
Each direction offers inroads against barriers. But most complexity questions remain wide open, without consensus on when they will be solved. The infinity of complexity classes between P and NP, as well as beyond, lays out an uncharted ladder of possibilities ascending to great heights from where we stand today. Ongoing step-by-step progress expands and solidifies what footholds exist on this vertical climb.
Example Codes Demonstrating Hardness
Here we provide some examples of code for NP-hard problems like clique, SAT, and TSP to illustrate hardness manifested in programs:
boolean hasClique(Graph g, int k) {
// Exact but exponential check of all k-node subsets
for S in powerset(g.nodes, k)
if (S is a clique in g)
return true;
return false;
}
boolean isSatisfiable(BooleanFormula f) {
// Check all 2^n variable assignments
for b in {0, 1}^n
if (b satisfies f)
return true;
return false;
}
int solveTSP(int[] distances) {
// Check all orderings
int bestDist = MAX_VALUE;
for p in permutations(cities)
if (cost(p) < bestDist)
bestDist = cost(p);
return bestDist;
}
The exponential checks encapsulate the hardness. No polynomial-time solutions are known for these problems or thousands of other NP-complete problems despite decades of research by brilliant computer scientists.
