uplinks:: Computer Science
tags:: #lang/en #note/develop

P versus NP Problem

A major unsolved problem in computer science
$P$ : all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time
$NP$ : all decision problems whose answer is "yes" and can be verified in polynomial time by a deterministic Turing machine, or problems that are solvable in polynomial time by a nondeterministic Turing machine
The answer to the problem would determine whether problems that can be verified in polynomial time can also be solved in polynomial time.
It is widely believed that $P \neq NP$ , which means that there are problems in $NP$ that are harder to compute than to verify and could not be solved in polynomial time, but their answers could be verified in polynomial time.

References