Guessing (Nondeterministic Turing Machine)

Definition

Guessing (Nondeterministic Turing Machine)

Guessing is the existential phase of a nondeterministic Turing machine: on input $x$, the machine selects one possible sequence of nondeterministic choices, represented by a finite string $y$. A deterministic verification phase then checks whether $y$ describes an accepting computation or a valid candidate solution.

If $V$ is the resulting deterministic verifier, then

$$x\in L(M)⟺\exists y\in {\Sigma }^{\ast }:V(x,y)=1.$$

The existential quantifier expresses that only one computation branch needs to accept. The string $y$ is a certificate (or witness) for $x$; it may encode either the branch’s nondeterministic choices or the candidate object checked by the verifier.

Guessing as Generation

The guessing phase can be viewed as a generator rather than as a verifier. For an input $x$, let

$$G_M(x)=\{y\in {\Sigma }^{\ast }\mid y\text{ can be generated by a computation branch of }M\text{ on }x\}.$$

The generator produces possible candidates; it does not determine whether they are correct. A separate verification phase tests each candidate with a predicate $V$:

$$V(x,y)=1⟺(x,y)\in R,$$

where $R$ is a polynomially decidable binary relation. The NTM accepts precisely when the generated set contains a verified candidate:

$$x\in L(M)⟺\exists y\in G_M(x):V(x,y)=1.$$

This distinction matters because generation supplies the existential search space, whereas verification checks a candidate against the required relation. A polynomially balanced binary relation additionally bounds the length of the generated candidates by a polynomial in $|x|$; polynomial decidability then makes their verification efficient.