patternMinor
Why is SAT in NP?
Viewed 0 times
satwhystackoverflow
Problem
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?
Solution
CNF-SAT is in NP since you can verify a satisfying assignment in polynomial time. CNF-SAT is NP-hard since SAT is a special case of CNF-SAT, and so we can reduce the NP-hard problem SAT to the CNF-SAT. Since it is both in NP and NP-hard, we conclude that CNF-SAT is NP-complete.
Context
StackExchange Computer Science Q#23353, answer score: 3
Revisions (0)
No revisions yet.