4 ms·
> Solving a hard problem with code doesn't mean that you solved the general case. If we're talking about P=NP, 3-SAT is the "general case". That's why I picked
by erichocean 8y ago
> Solving a hard problem with code doesn't mean that you solved the general case.
If we're talking about P=NP, 3-SAT is the "general case". That's why I picked it, since all NP problems are reducible to 3-SAT in polynomial time and space.
- jcranmer 8y agoSaying that you solve a specific case of satisfiability problems (e.g., siphash) is not proof that you can solve any 3-SAT problem. Graph coloring is a great example of this phenomenon--graph coloring is NP-hard, but most graphs can be colored very efficiently in polynomial time.