# The Sat Problem is NP-complete!!!!!

## Recommended Posts

Hello,

I cant understand how to proof cook's theorem.

Especially, i cant undertand proof on book of Computers and Intractability.

best regards...

##### Share on other sites

N-SAT problem is NP-Complete, the Binary-SAT problem is its simple version

Cook-Levin theorem is very important, because it doesn't only prove that n-SAT is an NP problem .. but also it

proves that any NP problem can be reduced in a pynomial time to a finite turing machine with boolean satisfaction problem

Edited by khaled
##### Share on other sites

Thank you very much,

i know that cook theorem very important but i dont understand this proof:( i need a illumunating sketchy!

<br class="Apple-interchange-newline">

N-SAT problem is NP-Complete, the Binary-SAT problem is its simple version

Cook-Levin theorem is very important, because it doesn't only prove that n-SAT is an NP problem .. but also it

proves that any NP problem can be reduced in a pynomial time to a finite turing machine with boolean satisfaction problem

##### Share on other sites

Thank you very much,

i know that cook theorem very important but i dont understand this proof:( i need a illumunating sketchy!

<br class="Apple-interchange-newline">

You might not understand the formal proof, because they don't mention all details, here is a simple proof: ProofWiki:Cook-Levin

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account