3 ms·
So what you're saying is: If there exists an algorithm that always guesses correctly then we can solve NP problems? That's just the definition of NP restated.
by bawolff 5y ago
So what you're saying is:
If there exists an algorithm that always guesses correctly then we can solve NP problems?
That's just the definition of NP restated. One of the definitions of NP is all the problems that can be solved in polynomial time if at every choice we had a method of always guessing correctly.
The question of NP=P is if such a method can actually be implemented in polynomial time on a Turing machine.
So yes, you are correct, it stands to reason that if NP=P, then NP=P.
- hnfong 5y agoI don't know whether the GP intends this, but one fun way of understanding the GP's comment is: If you believe really so strongly that P!=NP without actual proof, you're actually just making a guess, and then saying you can make good guesses. But the process of doing so implies you actually believe P=NP.