Editing NP (complexity) (section)

== Equivalence of definitions ==
The two definitions of NP as the class of problems solvable by a nondeterministic [[Turing machine]] (TM) in polynomial time and the class of problems verifiable by a deterministic Turing machine in polynomial time are equivalent. The proof is described by many textbooks, for example, Sipser's ''Introduction to the Theory of Computation'', section 7.3.

To show this, first, suppose we have a deterministic verifier. A non-deterministic machine can simply nondeterministically run the verifier on all possible proof strings (this requires only polynomially many steps because it can nondeterministically choose the next character in the proof string in each step, and the length of the proof string must be polynomially bounded). If any proof is valid, some path will accept; if no proof is valid, the string is not in the language and it will reject.

Conversely, suppose we have a non-deterministic TM called A accepting a given language L. At each of its polynomially many steps, the machine's [[computation tree]] branches in at most a finite number of directions. There must be at least one accepting path, and the string describing this path is the proof supplied to the verifier. The verifier can then deterministically simulate A, following only the accepting path, and verifying that it accepts at the end. If A rejects the input, there is no accepting path, and the verifier will always reject.