3 ms·

Isn’t UP complete with respect to CNF satisfiability though? How does P completeness relate to parallelizability of SAT?

• fooker 3y ago
  It's related in the sense that we can guarantee that all threads have to communicate at every step of the algorithm. It's not a deal breaker, but we really need some unprecedented advance in mathematics to negate this or to solve SAT without this communication.
  • bmc7505 3y ago
    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).
    • fooker 3y ago
      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.