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

[selcuk]

Hello,

 

I cant understand how to proof cook's theorem.

 

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

 

Please help me about how to understand simply this proof.

 

 

best regards...

[khaled]

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 December 20, 2011 by khaled

[selcuk]

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

[khaled]

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