2 ms·
Maybe you should actually state Cook's theorem. :-) (It states that k-SAT is NP-complete, btw.) Why is it important? It was the first result that identified a
by pmiller2 17y ago
Maybe you should actually state Cook's theorem. :-) (It states that k-SAT is NP-complete, btw.)
Why is it important? It was the first result that identified a naturally-occurring, NP-complete problem. Thanks to Cook's theorem, to prove that problem X is NP-complete, we can always use the strategy of providing a polynomial-time reduction from k-SAT to problem X.