Define classes P,NP,NP hard and NP-complete and also explain their relationship diagrammatically. What is nondeterministic algorithm? Explain with example. Define circuit satisfiability problem and prove that circuit SAT is in NP class.
P-P is the set of decision (or optimization) problems that can be solved by a deterministic algorithm in polynomial time, i.e. O(nk) time where n is the input size and K is non negative value independent of n.
NP-NP is the set of all problems, which are verifiable in polynomial amount of time. An algorithm is called NP if the algorithm has two parts-1)guessing part 2) verification part and this verification must be completed in polynomial time by a deterministic algorithm.
NP hard(NPH)- A problem L is said to be NP hard if for any problem A€NPH, A can be polynomially reducible to L.
NP-Complete(NPC)- A problem L is said to be NP-complete(NPC), if L€NP and for every problem A€NP,A is polynomially reducible to L.
Nondeterministic algorithm:
A algorithm is said to be non-deterministic if the algorithm has two parts-1) guessing part 2) verification part and this verification must be completed in polynomial time by a deterministic algorithm. Every non-deterministic algorithm has two parts:1) deterministic part 2) non deterministic part. The guessing part is the non-deterministic part and the verification part is the deterministic part. For eg: suppose we are standing at a position A and we have to reach to B by taking a path. The guessing part that which part we should take is non deterministic and the verification of our guess is deterministic.
circuit satisfiability (CIRCUIT SAT)problem is the decision problem of determining whether a given Boolean circuit has an assignment of its inputs that makes the output true.
CIRCUIT SAT is in NP
Proof: we first use the choose method to guess the values of the input nodes as well as the output value of each logic gate. Then we simply visit each logic gate g in C, i.e each vertex with at least one incoming edge. We then check the guessed value for the output of g is in fact the correct value for g’s Boolean function based on the given values for the input of g. this evaluation process can easily be performed in polynomial time. If any check for a gate fails, or if the guessed part value for the output is 0 then we output “no”. if on the , the check for every gate succeeds and the output is 1 the algorithm outputs “yes”. Thus if there is indeed a satisfying assignment of input values for C, then there is a possible collection of outcomes to the choose statements so that the algorithm will output “yes” in polynomial time. Likewise, if there is a collection of outcomes to the choose statements so that the algorithm outputs “yes” in polynomial time algorithm, there must be a satisfying assignment of input values for C. therefore CIRCUIT SAT is in NP.