The Power Of Nondeterminism And The Dtime Hierarchy

Definition of nondeterminism and nondeterministic Turing machines

A nondeterministic Turing machine (NDTM) is a theoretical model of computation that extends the standard deterministic Turing machine (DTM) with an additional capability: at each step in its operation, an NDTM can transition into any one of multiple possible next states, rather than just a single determined next state. This ability for multiple possible computational paths introduces nondeterminism into the model.

Formally, an NDTM M is defined with components (Q, Σ, Γ, δ, q0, qaccept, qreject) just like a standard DTM, except the transition function δ maps Q x Γ → P(Q x Γ x {L,R}) instead of Q x Γ → Q x Γ x {L,R}. Here, P denotes the power set. So for any given state and symbol under its tape head, an NDTM can transition nondeterministically into multiple possible next configurations.

An input string w is accepted by M if there exists any sequence of nondeterministic choices leading M from the initial configuration on w to an accepting configuration. The complexity class NTIME(f(n)) is then defined as the set of languages L decidable by an O(f(n)) time NDTM.

Nondeterministic time complexity classes such as NTIME(f(n))

Nondeterministic analogues exist for all the standard deterministic complexity classes. Some key nondeterministic classes include:

• NTIME(f(n)) – Problems solvable in O(f(n)) time on an NDTM
• NL – Problems solvable in O(log n) time on an NDTM
• NP – Problems solvable in polynomial time O(n^k) on an NDTM for some constant k
• NEXPTIME – Problems solvable in exponential time 2^O(f(n)) on an NDTM for some f(n)

The most well-studied of these is of course NP, which captures the concept of “efficiently verifiable” computation and contains many important problems related to optimization, scheduling, reasoning, and more. Though we do not know if P = NP, most evidence indicates the two classes are likely distinct.

Relationship between nondeterministic and deterministic time: NTIME(f(n)) ⊆ DTIME(2^f(n))

A useful theorem relates the power of nondeterministic computation to its deterministic counterpart: for any “nice” time-constructible function f(n), we have

In other words, any problem solvable in O(f(n)) nondeterministic time can be solved in 2^O(f(n)) deterministic time. So there is at most an exponential separation between deterministic and nondeterministic computation for a given resource bound.

The proof of this result uses a step-by-step simulation argument: A DTM can simulate an NDTM by following all possible computational paths of the NDTM in a tree-like branching manner. Because the NDTM runs for at most O(f(n)) steps along any path, the total size of this tree is bounded by 2^O(f(n)) configurations.

The deterministic time hierarchy theorem

The deterministic time hierarchy theorem is a seminal result in computational complexity that shows how increasing deterministic time resources allows solving strictly harder languages:

Here DTIME(f(n)) ( DTIME(g(n)) denotes a proper subset relationship. In words: given “slightly more” deterministic time, strictly more languages become decidable. The canonical proof constructs an arbitrary language L in DTIME(g(n)) that encodes the execution table of a f(n)-time DTM, then diagonalizes against all such machines to make L undecidable in DTIME(f(n)).

The significance of this theorem is in showing that there is an infinite deterministic time hierarchy – there are an infinite number of strictly harder languages decidable given more deterministic time resources. Thus no single deterministic resource bound captures all efficiently decidable languages.

The nondeterministic time hierarchy theorem

An analogous nondeterministic time hierarchy theorem holds relating NTIME complexity classes:

Thus given “slightly more” nondeterministic time, strictly more languages are nondeterministically decidable. The proof of this theorem follows that of the deterministic case but must handle subtle issues arising from the nondeterministic computation model. We sketch the proof next.

Formal statement and proof sketch of the nondeterministic time hierarchy theorem

We now formally state and prove the nondeterministic time hierarchy theorem. Let M₁, M₂, … denote enumerations of NDTMs.

Proof Sketch. Let h(n) = 2^f(n). We construct a language L as follows:

A string w is in L iff:

1. |w| encodes the entire configuration table of M_i on input 0ⁿ for some i and n
2. M_i has runtime bounded by f(n) on all paths
3. There exists some accepting path of M_i on 0ⁿ not traced out by computation table encoded in w

Intuitively, we use w as an “execution table” to witness that M_i accepts 0ⁿ within f(n) time along some path, but diagonalize by requiring the table to omit the actual accepting path taken by M_i.

To complete the argument, we show:

1. L ∈ NTIME(g(n)): An NDTM N with g(n) time can nondeterministically guess i, n, the accepting path of M_i omitted from w, then verify that w meets the criteria.
2. L ∉ NTIME(f(n)): Any NDTM N' attempting to decide L sees only a partial configuration graph of M_i from the table encoded in w. If N' has < 2^f(n) time, it cannot explore the full configuration tree of M_i and so cannot rule out additional accepting paths not encoded in w, forcing N' to reject even some w ∈ L.

∎

The last step crucially relies on limits of deterministic simulation of nondeterministic machines to establish the separation NTIME(f(n)) ( NTIME(g(n)).

Implications of the nondeterministic time hierarchy

The nondeterministic time hierarchy theorem has several important implications:

1. No optimal nondeterministic time bound: No single nondeterministic time bound suffices to capture all feasible nondeterministic computation. Given more nondeterministic time resources, strictly more problems become nondeterministically solvable.
2. NL ( NP: Setting f(n) = log n and g(n) = n^k gives NL ( NP, resolving an open question about small nondeterministic classes.
3. NEXPTIME not equal to NP: Choosing exponential gap functions proves NEXPTIME has strictly more power than NP.
4. Structure within NP: Intermediate nondeterministic classes exist between NL and NP.

Thus the nondeterministic time hierarchy carves out rich structure in nondeterministic complexity classes analogously to the deterministic hierarchy theorems.

Examples of problems in different levels of the nondeterministic time hierarchy

We present some example problems naturally falling into different nondeterministic time complexity classes:

• NL: ST-Connectivity, Graph Non-Isomorphism
• NP-intermediate classes: Vertex Cover, Set Splitting
• NP: Clique, Subset Sum, 3SAT, Hamilton Path
• NEXPTIME-complete: Succinct 3SAT, Generalized Chess

While hundreds of natural NP problems are known, far fewer complete problems have been established for small nondeterministic classes like NL or intermediate classes between NL and NP. Discovering complete problems for these classes remains an active research direction.

Open questions regarding nondeterministic computation

Open questions abound regarding nondeterministic complexity classes:

• Does NL = NP hold? This remains perhaps the most prominent open question after P vs NP.
• Are there complexity classes between NL and NP? Some candidate intermediate classes have been proposed but their separation remains open.
• Does the nondeterministic time hierarchy “speed up” given different padding? Variants on the theorem’s hypotheses might strengthen the separation.
• Are there natural complete problems for small nondeterministic classes like NL? Their study could reveal deep structure about efficient nondeterminism.

Researchers continue working to resolve these questions and unlock the potential of nondeterminism as a computational resource.