4 ms·
Note that generating a grounding of boolean variables that satisfy a boolean expression is NP-complete (in general). That is just one of the many problem that l
by tlarkworthy 12y ago
Note that generating a grounding of boolean variables that satisfy a boolean expression is NP-complete (in general). That is just one of the many problem that lie a the bottom of conditional (if/else) logic (i.e. procedural programming).
- cpa 12y agoYes, 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]