- #1
David Carroll
- 181
- 13
I know that the Cook-Levin Theorem states that any NP-complete problem can be reduced to the Boolean Satisfiability Problem. I haven't actually perused the Theorem and I know it probably contains language that's above my ken, but I was wondering if anyone knew whether it is also true that any NP-complete problem can be reduced to any other NP-complete problem. Also: if the NP-complete problems can be reduced to the Boolean Satisfiability Problem, does it also follow that any polynomial-time solution to one NP-complete problem is able to be converted to a polynomial-time solution to the Boolean Satisfiability Problem?