3 ms·
That's not really a proof that we can't get a nice thing, though. SAT is NP-complete, but here we are talking about it. There may be ways to use parallelism at
by dgacmu 3y ago
That's not really a proof that we can't get a nice thing, though. SAT is NP-complete, but here we are talking about it. There may be ways to use parallelism at a higher level. And even if there isn't an alternative to unit propagation, a purely constant factor speedup with parallel processors isn't out of bounds and would still be fantastic.
- fooker 3y ago>a purely constant factor speedup with parallel processors isn't out of bounds and would still be fantastic. The state of the art with this is about 2x the speedup with an unbounded number of threads. That's not bad, but is not very useful because in most use cases of SAT you have multiple distinct problems solvable in parallel anyway.