Solvable v.s. Verifiable For a problem in p we have polynomial time algorithm to solve it For a problem in NP, we have polynomial time verification algorithm to verify a certificateSolvable V.S. Verifiable • For a problem in P, we have polynomial time algorithm to solve it • For a problem in NP, we have polynomial time verification algorithm to verify a certificate 9