3 ms·

A few mild disagreements over interpretation: 1. NP-hard problems are not necessarily hard for computers to solve; they are only hard in the worst case, which

by mjn 13y ago

A few mild disagreements over interpretation: 1. NP-hard problems are not necessarily hard for computers to solve; they are only hard in the worst case, which could be very rare for some NP-hard problems. SAT, for example, is the original canonical NP-complete problem. But in AI, it's nowadays seen as almost a canonical "fast bytecode". Other systems will often want to find a way to reduce their problem to SAT, because that reduction implies tractability, rather than intractability! If you can target SAT in your backend, you can rely on it (probably) being easy to solve, since most instances of SAT can be quickly disposed of by heuristic solvers. (The more common practical problem here is size blow-up in the reduction to SAT, rather than the SAT instance itself being hard to solve.) 2. Partly as a result of #1, the relevance of NP-hardness to cryptography in practice is often overstated. NP-hard problems aren't really hard in the relevant sense: worst-case harness is not sufficient for a one-way function. Attempts to construct one-way functions out of NP-hard primitives have a pretty poor record (not all have been broken, but a number have, and none have caught on). The other direction is true, though, that P=NP would imply no one-way functions. I wrote a bit more along these lines a while ago: http://www.kmjn.org/notes/nphard_not_always_hard.html http://www.kmjn.org/notes/nphard_not_always_hard.html

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.
mafribe 13y ago
Yes, NP-hardness is a worst-case notion, hence not easy to use in cryptography. But, once you know what algorithms and heuristics the SAT solver is using, it's usually not hard to concoct propositional formulae that the prover chokes on. It just happens to be the case that the formulae that humans typically want to get solved are easy for the algorithms we use. Quite why this is nobody really knows. Also, the reason we typically reduce NP hard-problems to SAT is not that SAT is somehow easier than other NP-hard problems, but because so much effort has been spent on optimising SAT solvers, unlike for almost all other NP-hard problems. As you say, when you reduce a problem to SAT, you typically loose a lot of structure. But the decades of research on SAT solvers more than compensate.
- mjn 13y ago
  I think it's mostly true that SAT-solvers are better because of decades of research/engineering on them. However there is some speculation that your observation that "you typically lose a lot of structure" is actually sometimes a win, because by "flattening" a representation it might allow some distant implicit constraints to propagate. In planning, for example, that's one hypothesis for where Graphplan and SATplan (two 1990s systems) got their win from, vs. traditional symbolic planners. Similar to a question that comes up in compilers, about optimizing high-level vs. low-level representations. High-level representations give you more specific semantic information, but turning everything into a flattened mud of combinator logic or CPS or SSA might allow for some whole-program optimizations that propagate originally-distant constraints.

by mjn 13y ago

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.

mafribe 13y ago

Yes, NP-hardness is a worst-case notion, hence not easy to use in cryptography. But, once you know what algorithms and heuristics the SAT solver is using, it's usually not hard to concoct propositional formulae that the prover chokes on. It just happens to be the case that the formulae that humans typically want to get solved are easy for the algorithms we use. Quite why this is nobody really knows. Also, the reason we typically reduce NP hard-problems to SAT is not that SAT is somehow easier than other NP-hard problems, but because so much effort has been spent on optimising SAT solvers, unlike for almost all other NP-hard problems. As you say, when you reduce a problem to SAT, you typically loose a lot of structure. But the decades of research on SAT solvers more than compensate.

mjn 13y ago
I think it's mostly true that SAT-solvers are better because of decades of research/engineering on them. However there is some speculation that your observation that "you typically lose a lot of structure" is actually sometimes a win, because by "flattening" a representation it might allow some distant implicit constraints to propagate. In planning, for example, that's one hypothesis for where Graphplan and SATplan (two 1990s systems) got their win from, vs. traditional symbolic planners. Similar to a question that comes up in compilers, about optimizing high-level vs. low-level representations. High-level representations give you more specific semantic information, but turning everything into a flattened mud of combinator logic or CPS or SSA might allow for some whole-program optimizations that propagate originally-distant constraints.