Comment by frutiger
4 years 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.
Yes.
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.
> 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.
(That you were trying to add and not correct was extremely unclear, FWIW.)
Thanks for the clarification!
Yes, interpreting NP as non-polynomial is a common misunderstanding. Especially because it's 'sort-of almost right'.