selcuk Posted December 17, 2011 Share Posted December 17, 2011 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... Link to comment Share on other sites More sharing options...
khaled Posted December 20, 2011 Share Posted December 20, 2011 (edited) 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 Link to comment Share on other sites More sharing options...
selcuk Posted December 23, 2011 Author Share Posted December 23, 2011 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 Link to comment Share on other sites More sharing options...
khaled Posted December 26, 2011 Share Posted December 26, 2011 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 Link to comment Share on other sites More sharing options...
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now