3 ms·

Similar to faster-than-light travel.

• geysersam 3y ago
  Really? Does parallel algorithms for SAT contradict any known laws of physics?
  • fooker 3y ago
    It contradicts mathematics. :) Unit propagation is P complete.
    • 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.
    • bmc7505 3y ago
      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.