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

Reply
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.

  • 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'.