Comment by eru

4 years ago

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.

3 comments

eru

frutiger 4 years 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.

saurik 4 years ago

(That you were trying to add and not correct was extremely unclear, FWIW.)
eru 4 years ago

Thanks for the clarification!
Yes, interpreting NP as non-polynomial is a common misunderstanding. Especially because it's 'sort-of almost right'.