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

INTRODUCTION TO NP-HARD AND NP-COMPLETENESS

 

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

 

Examples:

 

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)

 

 

 

1. PROBLEMS ARE IN NP?

 

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

 

 

 

Examples:

 

 

 

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.