1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: How to prove Satisfiability of boolean formulas is NP-complete

  1. Aug 7, 2012 #1
    How to prove "Satisfiability of boolean formulas is NP-complete"

    I can not figure out how to prove this. I have been trying to find something that explains it step by step, possibly even with an example. I can not find anything. Can somebody perhaps explain how you prove it or show me where I can find a thorough explanation ?
     
  2. jcsd
  3. Aug 9, 2012 #2

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Re: How to prove "Satisfiability of boolean formulas is NP-complete"

    Maybe this is what you are looking for:

    http://en.wikipedia.org/wiki/Cook–Levin_theorem
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook