3 ms·

A few more (though I love it when people write about one of my favorite topics!) 1. There are known algorithms for NP-complete problems that are "faster" than

by j2kun 13y ago

A few more (though I love it when people write about one of my favorite topics!) 1. There are known algorithms for NP-complete problems that are "faster" than checking all possible solutions (in fact, finding such algorithms have very big implications and make their discoverers very famous). They're just not all that much faster and certainly not polynomial-time, and hence they don't resolve P vs NP. For example, the third problem of finding the largest clique in a graph has the naive algorithm 3^n/3 of checking all solutions, but there is a long line of research improving this, and the fastest known algorithm today is a 2^0.249n algorithm. 2. The question of P vs NP is not the question of whether there are any genuinely difficult problems to solve, if by genuinely difficult we mean no poly-time solution. There are many problems out there that are known to have no polynomial time algorithm. There are even natural problems out there that are known to have no singly exponential time algorithm (i.e. the lower bound is 2^2^n). 3. The traveling salesman example is not correct: the traveller is limited in that he can only visit each city exactly once.

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.

by j2kun 13y ago

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.