A question about the Cook-Levin Theorem

[David Carroll]

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?

 

[Greg Bernhardt]

Thanks for the post! Sorry you aren't generating responses at the moment. Do you have any further information, come to any new conclusions or is it possible to reword the post?

 

[David Carroll]

I don't seem to have any further information. A couple years ago, I tried to reformulate any statement in Boolean logic into terms of positive integers and then see if factoring any of those integers would solve the satisfiability of Boolean statements. The only problem was, at the time I had thought I came up with a polynomial time algorithm that would factorize any integer. Turns out I didn't, and the whole excursion was rendered moot

 

[Dragonfall]

The answers are "yes" to both of your questions. Any NP problem can be reduced to an instance of an NP-complete problem. A polynomial-time solution to any NP-complete problem means polynomial-time solutions to every NP problem.

What you tried to do in your second post is similar to something called "arithmetization", which was a technique used to prove that IP = PSPACE and NEXP = MIP. There is a negative result which states that arithmetization alone can't be used to solve P vs. NP.

More info on arithmetization can be found at http://www.scottaaronson.com/papers/alg.pdf

 

[David Carroll]

:)Thank you very much, Dragonfall. That was very helpful and kind.