Re:What's your favorite math proof?
by pmiller2 on Monday December 07, 2009 @06:18PM
(#982492)
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.
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.