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(adsbygoogle = window.adsbygoogle || []).push({}); anyother NP-complete problem. Also: if the NP-complete problems can be reduced to the Boolean Satisfiability Problem, does it also follow that any polynomial-timesolutionto one NP-complete problem is able to be converted to a polynomial-time solution to the Boolean Satisfiability Problem?

**Physics Forums - The Fusion of Science and Community**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# A question about the Cook-Levin Theorem

Loading...

Similar Threads - question Cook Levin | Date |
---|---|

B Secondary Upper and Lower Bound QUESTION | Mar 10, 2018 |

B Find the missing energy value given a set of data (Hypothetical question) | Mar 3, 2018 |

B Simple question about compactness | Feb 22, 2018 |

B Beginner function question | Feb 17, 2018 |

Jeff Cook's number system | Jan 13, 2007 |

**Physics Forums - The Fusion of Science and Community**