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

1. Aug 7, 2012

### XodoX

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. Aug 9, 2012

### LCKurtz

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