Definition
Guessing (Nondeterministic Turing Machine)
Guessing is the existential phase of a nondeterministic Turing machine: on input
, the machine selects one possible sequence of nondeterministic choices, represented by a finite string . A deterministic verification phase then checks whether describes an accepting computation or a valid candidate solution. If
is the resulting deterministic verifier, then The existential quantifier expresses that only one computation branch needs to accept. The string
is a certificate (or witness) for ; 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
The generator produces possible candidates; it does not determine whether they are correct. A separate verification phase tests each candidate with a predicate
where
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