## 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, \(M_D\) can verify the solution in polynomial
time. Then one can construct a polynomial-time NTM, \(M_N\), which
‘chooses’ a certificate from among the set of possible
polynomial-length strings. 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).