Notes to Quantum Computing

1. Equivalently, the class NP can be characterised as the class that contains all those computational decision problems for which a proposed solution can be verified by a DTM in polynomial time given a “proof” of (i.e. a certificate for) that solution. The two definitions are equivalent. For a given problem and an NTM that solves it there is by definition a polynomial-length sequence of transitions of the NTM which will result in a particular solution. One can use this sequence as a certificate or “proof” of that solution which can then be fed to a DTM to verify it in polynomial time. Conversely, suppose there is a DTM $$M_D$$ which is such that, given a polynomial-length certificate for a particular solution, can verify it in polynomial time. Then one can construct a polynomial-time NTM $$M_N$$ which ‘chooses’ certificates from among the set of possible polynomial-length strings (e.g., by randomly writing one down). Upon choosing a certificate, $$M_N$$ then feeds that certificate to $$M_D$$, and transitions to ‘yes’ only if $$M_D$$ outputs ‘yes’ (Arora and Barak 2009, 42).

This is a file in the archives of the Stanford Encyclopedia of Philosophy.