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.

Ans

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.

atOptions = { 'key': 'a900f2dbf175e78754c26c6231a4b673', 'format': 'iframe', 'height': 90, 'width': 728, 'params': {} };

Related Questions