Re:The Silent (R)evolution of SAT
by bmc7505 on Friday May 26, 2023 @04:37PM
(#36089234)
I remain skeptical. NC=P? is still an open conjecture, so there could be problems which are decidable in P, but only when using a polynomial number of processors or superpolynomial on a single processor, but polynomial on a polynomial number of processors. Furthermore, the amortized complexity of common instances could turn out to be tractable on average (e.g., random 3-SAT instances are tractable unless they fall in a very narrow region where the ratio of clauses to variables is ~4.25, but NP-complete in the worst case).
[ Parent
| on HN ]
You're not wrong, but people have been trying to do this for a while now without much success.
So much that you can probably get a turing award by making a SAT solver that can be 100-1000x faster on a GPU than on a CPU.
Also that would lead to solving a bunch of NP complete problems 1000x faster, so you can see why that would be a big deal.