Cheap and Secure Web Hosting Provider : See Now

[Solved]: Why is SAT in NP?

, , No Comments
Problem Detail: 

I know that CNF SAT is in NP (and also NP-complete), because SAT is in NP and NP-complete. But what I don't understand is why? Is there anyone that can explain this?

Asked By : user2795095

Answered By : vzn

Try reading up on the Cook-Levin theorem. SAT is basically the first problem proven NP-complete. High level sketch of the proof: simulate a nondeterministic (NP-time, nondeterministic polynomial time) TM computation using a cascading circuit that computes the TM iterations, which can be converted to SAT. Loosely speaking, the "size" of the circuit is "polynomial".

Best Answer from StackOverflow

Question Source :

 Ask a Question

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback