Promise Problems And Intermediacy: Can Ladner’S Theorem Apply?

The Promise of Intermediacy

The field of computational complexity categorizes mathematical problems based on the resources required to solve them. Problems fall into complexity classes based on the time or space needed by algorithms to find solutions. Two important complexity classes are P and NP. P contains problems that can be solved in polynomial time by a deterministic Turing machine. NP contains problems where solutions can be verified in polynomial time, but finding those solutions may take exponential time.

An outstanding question in theoretical computer science is whether P equals NP. This is considered one of the greatest open problems in mathematics and computer science. Most experts believe P does not equal NP, implying there are computationally difficult problems in NP that are inherently intractable. However, proving P ≠ NP has so far defied mathematicians and computer scientists.

In 1972, Theodore Baker, John Gill, and Robert Solovay introduced the concept of intermediacy for complexity classes. A problem or language is intermediate if it lies in NP but not in P. The existence of intermediate problems sheds light on the structure of P and NP and their relationship. In particular, if any intermediate problems exist, it would show P ≠ NP.

Explaining Promise Problems

Closely related to intermediacy is the concept of a promise problem. A promise problem consists of promised or restricted inputs rather than completely arbitrary inputs. For example, in the SUBSET-SUM problem, the inputs are restricted to consist of integers instead of arbitrary strings. By considering promise versions, problems can have greater structure to analyze. Promise problems may potentially be easier to classify in terms of complexity.

Formally, a promise problem is a pair (Y,N) where Y and N are disjoint sets of strings over some alphabet. Y represents yes-instances that should be accepted, while N represents no-instances that must be rejected. An algorithm solves a promise problem if it always accepts strings in Y and rejects those in N. Importantly, the behavior on other inputs not in Y ∪ N is undefined.

Every classical decision problem maps to a trivial promise problem where Y contains just the yes-instances, N just the no-instances, and every other string is excluded. More interesting promise problems restrict but do not completely specify the inputs. This relaxation of requirements can change a problem’s complexity and enables finer-grained classifications.

Ladner’s Theorem and Its Implications

In 1975, Richard Ladner proved an influential theorem showing that if P ≠ NP, then promise problems with intermediate complexity must exist. Specifically, if P is a strict subset of NP, there is a language L in NP such that L is not in P and L is not NP-complete. The language L would therefore have intermediate status.

Ladner’s theorem implies the structure of problems in NP depends on whether P = NP. If P = NP, all problems in NP are either in P or NP-complete. No intermediate problems can occur. However, if P ≠ NP, NP problems can have multiple tiers of difficulty. At least one intermediate tier between P and the NP-complete problems must exist.

The power of Ladner’s theorem is it reveals intermediacy is inherently connected to the P vs. NP question. Proving any single problem has intermediate status would therefore resolve one of the deepest open questions in computer science by showing P ≠ NP. Unfortunately, despite much effort by researchers over decades, no intermediate problems have yet been found.

Intermediacy in P and NP

Classifying problems based on their worst-case run time leads to fairly coarse groupings. Both tractable and intractable problems can exist within the same complexity class. To enable more precision, the concepts of intermediacy and promise problems provide ways to refine classifications.

One approach is to isolate subsets of a class forming distinct intermediate degrees of difficulty. For example, number theorists study arithmetic circuit classes like ACC which finely stratify problems solvable by circuits with various growth rates. This reveals deeper internal structure despite the circuits all lying theoretically within P.

Another approach is to restrict inputs to create promise problem versions of languages. Promise problems provide more latitude in classifications since uncomputable or undecidable instances can be excluded by fiat. For example, while the VALIDITY promise problem is NP-complete, its restriction to boolean formulas in 3-CNF form places it potentially in P. Input restrictions fundamentally alter computational difficulty.

Intermediate promise problems also illuminate the gap between languages by spanning their differences. Constructing promise problems of graduated complexity could pave a path leading from lower classes to higher ones, elucidating the essential differences separating them. This knowledge helps characterize what fundamentally makes one class harder than another.

Constructing an Intermediate Problem

While Ladner’s theorem guarantees the existence of intermediate problems conditional on P ≠ NP, finding concrete examples remains challenging. To construct an intermediate promise problem, both harnessing and restricting hardness is necessary. The problem must be shown hard enough to not lie in P, yet also provably easier than any NP-complete language.

One promising approach is to leverage transformations between existing NP-complete problems. If a polynomial-time mapping reduction from a known hard problem can be found, but also crucially prevented from reaching full completeness via input restrictions, this can potentially isolate intermediate difficulty. The promise problem TEXT-MATCHING-3CNF constructed this way lies in NP by reduction from SATISFIABILITY-3CNF, but restricted clause lengths avoid full completeness.

Another fruitful direction is investigating problems in P with inputs restricted to make verification difficult. For example, the promise problem FACTORING-SEMIPRIMES requires factoring only semiprimes, not arbitrary integers. This places the problem in NP but also outside P based on cryptography. By carefully balancing restrictions with hardness proofs, similar approaches may uncover new intermediate problems.

Proof of Intermediacy

Proving a problem has genuinely intermediate status poses considerable challenges. Merely placing upper and lower bounds is insufficient since this does not exclude membership in P or NP-completeness. Constructing an intermediate problem therefore requires both embedding enough difficulty to avoid containment in P while also avoiding the traps leading to NP-hardness.

For the lower bound, a polynomial-time mapping reduction from a known hard problem can provide evidence of hardness. However, such reductions must avoid smuggling in excessive power to jump beyond NP-completeness. Hardness proofs require delicate handling of transformations between complexity classes to prevent crossing critical thresholds enabling completeness.

For the upper bound, restrictions on structure and resources certify containment within NP. Bounding solution lengths or the vocabulary for valid solutions limits expressive power below NP-completeness. Since the NP-complete problems capture the maximal difficulty within NP, carefully selected restrictions can cut off paths to completeness.

Combining restricted polynomial-time reductions with structural input promises can sandwich difficulty between P and NP-completeness. While finding the appropriate balance remains challenging, this two-pronged approach via restricted embeddings and structural promises holds the most potential for revealing concrete intermediate problems.

Applications of Intermediate Status

The discovery of any intermediate promise problem would have profound implications both for mathematics and computer science. Most importantly, it would resolve the P vs. NP question by exhibiting a separation. Additionally, intermediate problems generate insight into the barriers separating complexity classes and the frontiers where complexity phase transitions occur.

On the practical side, intermediate problems have useful applications in cryptography based on their presumed difficulty. Just as with factoring semiprimes, problems that are verifiable but not known to have polynomial-time solutions can yield cryptographic schemes secure against quantum attacks. Intermediate problems also inspire algorithmic techniques like approximation, randomization, and parallelization helpful for approaching intractability.

On the structural side, intermediate problems situate the sharp delineations in complexity hierarchies that characterize phase boundaries. Hardness phase transitions shed light on the thresholds differentiating easy from hard as well as feasible from infeasible computation. Understanding intermediate problems offers a window into the barriers separating complexity classes.

Open Questions on Promise and Intermediacy

While Ladner’s theorem demonstrates the conditional existence of intermediate problems, discovering explicit examples remains an open challenge despite intense research over decades. Both promise problems and classical languages so far frustratingly elude definitive classification between P and the NP-complete upper bound.

Nonetheless, deeper investigation of promise problems offers a path forward. By excluding pathological inputs, promise problems better model real-world computational tasks with underlying structure. Continuing to bridge promise problems with restricted versions of classically hard problems provides the most promising direction toward finally exhibiting intermediacy.

Resolution of these open questions surrounding intermediate promise problems could profoundly reshape our understanding of computational complexity. Determining whether intricately intertwined problems at the boundaries of tractability can be teased apart would elucidate essential differences between easy and hard computations. These discoveries could lead to fundamental advances in algorithms, cryptography, optimization, and beyond.