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!

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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: How to prove Satisfiability of boolean formulas is NP-complete
  1. NP-complete or not (Replies: 3)

  2. Boolean Algebra prove (Replies: 8)

Loading...