3 ms·
To expand on 2. above: It's a common misconception that the class NP is important because it stands for hard problems, but in fact there are classes of hard pro
by algorias 13y ago
To expand on 2. above: It's a common misconception that the class NP is important because it stands for hard problems, but in fact there are classes of hard problems which we know to be distinct from P. Specifically, P != EXPTIME (see the time hierarchy theorem).
The reason why the P vs NP question is interesting is the possibility of verifying solutions. We know there are easy problems, and we know there are hard problems, but we don't know if there are hard problems that are easy to verify. Intuitively, for many problems it's much easier to recognize a correct solution than come up with one. This is formalized by the statement P != NP, and in that light it's quite clear why the vast majority of researchers believe it to be true.