4 ms·
The “P” in NP means a solution to a decision problem is verifiable in polynomial time. The “N” in NP means the solution can be produced by a non-deterministic
by frutiger 5y ago
The “P” in NP means a solution to a decision problem is verifiable in polynomial time.
The “N” in NP means the solution can be produced by a non-deterministic Turing machine (i.e. a computer that can search the problem space in many dimensions in each step).
NP does not mean “non-polynomial” time to produce a solution, otherwise P != NP by definition. Instead P is a subset of NP.
The open question is if all decision problems with solutions verifiable in polynomial time can also be produced in polynomial time.
- deleted 5y ago[deleted]
- eru 5y agoYes. I know that the N stands for non-deterministic. Read my comment carefully, it agrees with everything you write here. (Or at least, does not disagree. It's silent on most of the intricacies.) For many people moving a problem from NP to P means the same as having a tractable solution. See eg Scott Aaronson's writing on the topic.
- frutiger 5y ago> Read my comment carefully Please take a spoon of your own medicine and read my comment even more carefully. I never suggested my comments were a contradiction to yours. I added some information for bystanders that may have read your comment and come to (or reinforced) a wrong conclusion.