[Solved]: Why is SAT in NP?

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 : http://cs.stackexchange.com/questions/23353

 Ask a Question

 Download Related Notes/Documents