4 ms·
Yes, it basically solves a SAT problem. But modern SAT solver are very very efficient. So although your worst case is exponential, in many cases heuristics will
by cpa 12y ago
Yes, it basically solves a SAT problem. But modern SAT solver are very very efficient. So although your worst case is exponential, in many cases heuristics will help find a solution very quickly. That's quite impressive; in fact, the motto "if you have a NP-hard problem just reduce it to SAT and throw a SAT solver on it" is becoming more and more common.
- tlarkworthy 12y agoNP-complete is an unbreakable wall, strewn with the bloodied corpses of enthusiastic heuristic authors. You can only break it if your problem domain was never NP-hard in the first place (e.g. sparse or some other exploitable structural features). Very very fast means nothing on a true NP-hard problem for quite modest n. Note the author had to include a spurious constraint to get his system to converge, despite it being quite a small task in the first place. My point was that this approach has fundamental reasons why it won't scale to real programming tasks, of which the interesting ones that programmers get wrong all the time are likely to be the true NP-complete type.
- deleted 12y ago[deleted]