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(

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

A * 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*

*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 |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

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