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