## 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).