1
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by David Richerby, D.W. Jun 20 '17 at 22:32

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are those definitions equivalent, though? $\endgroup$ – J. Antonio Perez Jun 20 '17 at 18:33
  • $\begingroup$ 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. $\endgroup$ – fade2black Jun 20 '17 at 19:00
  • $\begingroup$ 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. $\endgroup$ – J. Antonio Perez Jun 20 '17 at 19:18
  • $\begingroup$ 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. $\endgroup$ – fade2black Jun 20 '17 at 19:26

Not the answer you're looking for? Browse other questions tagged or ask your own question.