# Does NP mean verifiable in polynomial time or solvable in polynomial time? [duplicate]

Is NP defined as verifiable in polynomial time, or solvable in polynomial time? Verifiable meaning that the solution can be checked in polynomial time, and solvable meaning that the solution can be found in polynomial time?

## 1 Answer

NP is a class of problems whose solution is verifiable in polynomial time on a deterministic Turing machine. Alternatively, NP is a class of problems whose solution is solvable in polynomial time on a nondeterministic Turing machine.

Please look here.

• Are those definitions equivalent, though? – Alecto Irene Perez Jun 20 '17 at 18:33
• I would say these definitions are different but result in the same class of problems, NP. You can easily prove that any problem verifiable in polynomial time on a deterministic TM is solvable on in polynomial time on a nondeterministic TM and vise versa. Advantage of the first definition (via verifiable) is that it is easy to show that given a solution it is verifiable in polynomial time, rather than come up with a nondeterministic TM solving the problem in polynomial time. – fade2black Jun 20 '17 at 19:00
• So... NP-complete problems are NP, but we don't have a polynomial-time algorithm (deterministic or non-deterministic) to solve any NP-complete problem. – Alecto Irene Perez Jun 20 '17 at 19:18
• NP-complete problems are NP-hard problems (every problem in NP-class is reducible to them) which belong in NP-class. Whether or not there is a polynomial time algorithm (running on a deterministic TM) that solves an NP-complete problem is a long standing mystery. You should have heard about the cliche P = NP problem. People believe these classes are not equal. – fade2black Jun 20 '17 at 19:26