3 ms·

As a nit, I think the vast majority cannot be solved fast? A large number of interesting ones can, though. Right?

• hansvm 4y ago
  Maybe (can't remember, might have never known), but not necessarily. As an example of the idea, consider the simplex algorithm as it applies to linear programming. It has exponential worst-case behavior, but people noticed that in practice the vast majority of interesting problems could be solved quickly. Later it was shown that all non-polynomial inputs do actually lie in some diminutive subspace.
  • AnimalMuppet 4y ago
    "Vast majority" and "vast majority of interesting ones" may be completely different. The vast majority are just random; the vast majority of interesting ones will have some kind of structure, given by the real-world problem they represent.
• beisner 4y ago
  As I understand it, I think that any randomly generated SAT problem will not be able to be solved quickly; however, SAT problems in the real world, even when they're large, tend to be quick for SAT solvers (most people solve the "Wedding Seating" problem for their own weddings, after all!), Why ordinary SAT problems tend to be easy to solve, last I checked was an open problem.
  • deleted 4y ago
    [deleted]
• ComplexSystems 4y ago
  The "vast majority" of SAT instances would be something like a SAT instance you would draw uniformly at random from some kind of distribution on all possible circuits. Making this idea rigorous is what k-random SAT is all about. It turns out that most randomly generated SAT instances in this way will lack certain features that tend to make industrial instances "hard," and in fact there is research on randomly generating random SAT instances which have those features and thus which are more difficult to solve. For instance: https://dl.acm.org/doi/fullHtml/10.1145/3385651 https://dl.acm.org/doi/fullHtml/10.1145/3385651