3 ms·
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 processor
by 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 agoYou'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.