The Nondeterministic Time Hierarchy And Issues With Common Statements
Defining Nondeterministic Time Complexity Classes
A nondeterministic Turing machine is a theoretical model of computation that, unlike a standard deterministic Turing machine, can follow multiple computational paths simultaneously. Formally, a nondeterministic Turing machine has a separate transition function that, for each combination of current state and symbol being read, specifies any number of possible next states rather than just one next state.
This ability to bifurcate its computation allows a nondeterministic Turing machine to solve problems more efficiently than deterministic machines in some cases. Computational complexity classes such as NP and co-NP are defined in terms of nondeterministic machines. For example, NP consists of all decision problems for which a “yes” answer can be verified by a polynomial-time nondeterministic Turing machine.
Relationship Between Deterministic and Nondeterministic Classes
An important open question in theoretical computer science is whether the deterministic class P is equal to the nondeterministic class NP. Most computer scientists conjecture that P does not equal NP, which would indicate there are efficiently verifiable problems that do not have efficient solutions on deterministic machines. However, despite intense study, there remains no proof separating these complexity classes.
Other nondeterministic complexity classes demonstrate strict set containment relationships with their deterministic counterparts. For example, it is known that nondeterministic logarithmic space (NL) is contained within P. Many complexity classes have robust containment hierarchies based on bounding various computational resources such as time and space.
Explaining the Nondeterministic Time Hierarchy Theorem
Time Hierarchy for Nondeterministic Complexity
The time hierarchy theorem demonstrates that for nondeterministic computation, increasing running time strictly increases computational power, similar to the hierarchy known to exist between deterministic time complexity classes. Formally, the nondeterministic time hierarchy theorem shows that for any constructible function f(n), the complexity class NTIME(f(n)) is properly contained within NTIME(g(n)) if g(n) dominates f(n), that is, if g(n)/f(n) goes to infinity as n grows arbitrarily large.
Intuition Behind the Hierarchy Result
The intuition is that if a nondeterministic Turing machine has more time, it can explore a larger branching tree of possible solutions. With enough additional time, problems can be solved that cannot be verified effectively within the shorter time bound. This argument relies crucially on the fact that nondeterministic algorithms produce solution certificates that can be quickly checked by deterministic verifiers.
Formal Statement and Proof Idea
The formal statement of the theorem is that for any constructible, monotonically increasing function f(n), if g(n) = f(n+1), then NTIME(f(n)) ⊊ NTIME(g(n)). The proof proceeds via diagonalization, showing the existence of a language decidable in g(n) time but not in f(n) time. An adversarial strategy is used, where the diagonal language consists of instances designed to specifically thwart machines operating within the f(n) time bound.
Challenging Common Misconceptions
Conflating Nondeterminism with Parallelism
A common misconception is thinking nondeterminism allows computation to occur in parallel, along multiple paths at once. While related to parallelism, nondeterminism merely represents the ability of a machine to non-strictly follow one of many possible computational branches.
True parallelism involves simultaneously computing along multiple paths, while nondeterminism implies a solution exists along some path without specifying precisely how that path gets followed. This distinction is subtle but important when reasoning about nondeterministic complexity classes.
Assuming Equality of Complexity Classes
Because nondeterminism is an abstract machine model not manifested in physical computers, some assume NP = P based on an lack of intuition separating the classes. However the time hierarchy theorem provides evidence that more time allows nondeterministic machines to explore larger solution spaces.
Additionally, problems in NP but not known to be in P exist, suggesting the classes are likely distinct. While equality of P and NP remains possible, no proof exists and most evidence suggests otherwise.
Overgeneralizing Hierarchy Results
The nondeterministic time hierarchy applies specifically to time bounds, not other resource bounds. Space-bounded complexity classes for example do not demonstrate an analogous robust hierarchy. Additionally, the result does not preclude collapse of lower time complexity classes, such as LOGTIME, to higher ones like P.
So while more nondeterministic time demonstrably yields more computational power, similar hierarchy relationships do not necessarily hold between other complexity measure bounds.
Applying the Hierarchy Theory in Practice
Using the Hierarchy in Algorithm Analysis
When analyzing nondeterministic algorithmic complexity, we apply time hierarchy theorems to demonstrate separations. For problems requiring high polynomial time, we invoke the hierarchy to argue those problems do not lie in low-degree polynomial time complexity classes unless the hierarchy collapses.
Relating the Hierarchy to Problems in P
Since P ⊆ NP, the time hierarchy theorem implies problems with solutions verifiable in n log n time cannot have deterministic polynomial time solutions without the hierarchy collapsing to P = NP. This helps relate nondeterministic claims about problems to consequences for deterministic algorithms.
Open Questions on Nondeterministic Complexity
While robust nondeterministic time hierarchies exist, open questions remain about more nuanced relationships between complexity classes. For example, does NP have complete problems under log-space reductions? Does co-NP = NP? Research on structural complexity theory persists in resolving these questions about nondeterminism.
