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?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
answered Jun 20, 2017 at 17:47
-
$\begingroup$ Are those definitions equivalent, though? $\endgroup$– AlectoCommented Jun 20, 2017 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$ Commented Jun 20, 2017 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$– AlectoCommented Jun 20, 2017 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$ Commented Jun 20, 2017 at 19:26