. . . "That is, given an input to a problem , there is a string called a certificate and a Turing machine for which verifies that proves and runs in polynomial time." .