Home | | User Interface Design | NP Hard and NP Completeness

Chapter: Analysis and Design of Algorithm : Traversals, Branch and Bound

NP Hard and NP Completeness

NP (nondeterministic polynomial): class of decision problems whose proposed solutions can be verified in polynomial time = solvable by a nondeterministic polynomial algorithm



P: the class of decision problems that are solvable in O(p(n)) time, where p(n) is a polynomial of problem‘s input size n




b  searching


b element uniqueness b graph connectivity b graph acyclicity


primality testing (finally proved in 2002)



NP (nondeterministic polynomial): class of decision problems whose proposed solutions can be verified in polynomial time = solvable by a nondeterministic polynomial algorithm


nondeterministic polynomial algorithm is an abstract two-stage procedure that: b generates a random string purported to solve the problem


b  checks whether this solution is correct in polynomial time



E.g. Problem: Is a boolean expression in its conjunctive normal form (CNF) satisfiable, i.e., are there values of its variables that makes it true?


This problem is in NP. Nondeterministic algorithm: b Guess truth assignment


b Substitute the values into the CNF formula to see if it evaluates to true Example: (A | ¬B | ¬C) & (A | B) & (¬B | ¬D | E) & (¬D | ¬E)


Truth assignments:


A B C D E 0 0 0 0 0


.  .  .


1 1 1 1 1


Checking phase: O(n)






b  Hamiltonian circuit existence


b       Partition problem: Is it possible to partition a set of n integers into two disjoint subsets with the same sum?


b       Decision versions of TSP, knapsack problem, graph coloring, and many other combinatorial optimization problems. (Few exceptions include: MST, shortest paths)


b       All the problems in P can also be solved in this manner (but no guessing is necessary), so we have:


 P inculde NP


b  Big question:  P = NP ?


NP problems


NP Hard problem:


–   Most problems discussed are efficient (poly time)


–   An interesting set of hard problems: NP-complete.



         A decision problem D is NP-complete if it‘s as hard as any problem in NP, i.e.,  D is in NP

  every problem in NP is polynomial-time reducible to D


Cook’s theorem (1971): CNF-sat is NP-complete



Other NP-complete problems obtained through polynomial-time reductions from a known NP-complete problem






Fig: NP Problems








TSP, knapsack, partition, graph-coloring and hundreds of other problems of combinatorial nature




v   P = NP would imply that every problem in NP, including all NP-complete problems, could be solved in polynomial time


v   If a polynomial-time algorithm for just one NP-complete problem is discovered,




then every problem in NP can be solved in polynomial time, i.e., P = NP


v        Most but not all researchers believe that P NP , i.e. P is a proper subset of NP

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Analysis and Design of Algorithm : Traversals, Branch and Bound : NP Hard and NP Completeness |

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.