Definition
Verification (Nondeterministic Turing Machine)
Verification is the deterministic phase that checks a fixed candidate produced by the guessing phase. Given an input
and a candidate , a verifier decides whether is valid for : where
is the relation being verified. The verifier does not generate candidates or search through alternatives; it evaluates the one candidate supplied to it. In the NTM’s guess-and-verify view, Thus, guessing supplies the existential choice, while verification checks its correctness. If
is a polynomially decidable binary relation, the verification runs in polynomial time.