Question

Prove that each of the problems below is in the NP class.
4-SAT problem
Instance: A Boolean expression E in FNC (normal connective forms),
Question: Are there at least four different solutions that make E satisfactory?

Answer 1

A problem is said to be in NP class if a solution set is given we can verify the problem in polynomial time .

4-SAT problem is a special case in SAT problem, SAT problem is the first problem that is proved to be NP-hard

Let's consider a turing machine that verifies the 4- SAT problem, it will take all the clauses and Simply plug the the solution set into the clauses and we can verify whether the assignment is acceptiong or rejecting instance in polynomial time ,if all clauses satisfies the solution set returns 1 else returns 0 ,Hence we can clearly see we can verify 4-SAT problem in polynomial time and depends on number of clauses ,Hence 4-SAT is in NP class