Design and analysis of algorithms Unit-V NP HARD AND NP complete

DAA Unit-V NP HARD AND NP complete

1. Unit-V
NP-HARD AND
NP-COMPLETE

2. Basic concepts
•We are concerned with distinction
between the problems that can be solved
by polynomial time algorithm and
problems for which no polynomial time
algorithm is known.
•Example for the first group is ordered
searching its time complexity is O (log n)
time complexity of sorting is O (n log n).

3. •The second group is made up of problems
whose known algorithms are non
polynomial. Example:-Traveling sales
person problem and knapsack problem for
which the best algorithms have time
complexities O(n
2
2
n
) and (2
n\2
)
respectively

4. •Here we do is show that many of the
problems for which there are no
polynomial time algorithms are
computationally related
•These are given the names NP hard and
NP complete

5. •A problem that is NP complete has the
property that it can be solved in polynomial
time iff all other NP complete problem can
be solved in polynomial time
•If an NP hard problem can be solved in
polynomial time ,then all NP complete
problem can be solved in polynomial time.

6. •All NP-complete problems are NP-hard.
but some NP-hard problems are not
known to be NP-complete

7. NON DETERMINISTIC
ALGORITHMS
•Algorithms with following property are
termed deterministic algorithm.
The result of every operation is uniquely
determined.

8. •We can allow algorithms to contain
operations whose outcomes are not
uniquely defined but are limited to
specified set of possibilites
•The machine executing such type of
operations is allowed to choose any of
these outcomes subjected to a termination
condition to be defined later

9. •To specify such algorithms, we define
three new function
•Choice(s)
•Failure()
•Success()
•X:=choice(1,n)could result in x being
assigned any one of the integers in
range[1,n]

10. •A nondeterministic algorithm terminating
unsuccessfully if and only if there exist no
set of choice leading to successful signals
•

11. •Any problem for which answer is either
zero or one is called decision problem
•An algorithm for a decision problem is
called a decision algorithm
•The satisfiability problem is to determine
whether the formulae is true for some
assignment of truth values to the variables

12. The classes NP- hard and NP-
complete
•An algorithm A is of polynomial complexity if
there exist a polynomial P() such that the
computing time of A is O(p(n)) for any input
size.
•P is the set of all decision problems solvable
by deterministic algorithms in polynomial
time
•NP is the set of all decision problems
solvable by nondeterministic algorithms in
polynomial time.

13. •Since deterministic algorithms are just a
special case of nondeterministic ones, we
conclude that P  NP.

14. •Definition: - Let L
1 and L
2 be two problems
.Problem L
1 reduces to L
2 if and only if
there is a way to solve L
1 by a
deterministic polynomial time algorithm
using a deterministic polynomial time
algorithm that solves L
2 in polynomial time
•ie, If we have a polynomial time algorithm
for L2 ,then we can solve L1in polynomial
time

15. •A Problem L is NP-hard if and only if it’s
satisfiability reduces to L
•A Problem L is NP-complete if and only if
L is NP-hard and LNP

16. NP
P

17. Commonlyb belived relationship
among P,NP,NP-complete and NP-
hard

P
NP
NP-hard
NP complete

18. •As an example of an NP hard decision
problem which is not NP complete
consider the example of halting problemfor
a deterministic algorithms
•The halting problem is to determine an
arbitrary deterministic algorithm A and
input I whether algorithm A with input I
ever terminates(or enters an infinite loop)

19. •It is well known that this problem is
undecidable .Hence there exist no algorithm
to solve the problem.so it cannot be in NP
•To show satifiability reduces to ( )the
halting problem
 simply construct an algorithm A
whose input is a prepositional formulaeX.If X
has n varables,then A tries out all 2
n

possible truth assignments and

20. Verifies whether X is satisfiable.If it is then
A stops,If it is not ,then A enters in an
infinite loop. Hence A halts on input X iff X
is satisfiable.If we had a polynomial time
Algorithm for the halting problem ,then we
could solve satisfiability problem in
polynomial time using A and X as input to
algorithm for the halting problem

21. •Hence the halting problem is an NP hard
decision problem which is not NP
complete

22. COOK’S THEOREM
Cook’s theorem states that satisfiability in P
if and only if P= NP
Proof:- We have already seen satisfiability
in NP
Given P=NP
Then satisfiability in p
It remains to show that if satisfiability in P
P=NP

23. •To do this, we show how to obtain from any
polyomial time nondeterministic decision
Algorithm A and input I a formula
Q(A,I)such that Q is satisfiable iff A has a
successful termination with input I
•If the length of I is n then then the time
complexity of A is p(n) for some polynomial
p(),then the length of Q is
O(p
3
(n) logn)= O(p
4
(n))

24. •The time needed to construct Q is also
O(p
3
(n) logn)
•A deterministic Algorithm Z to determine
outcome of A on any input I can be easily
obtained
•Algorithm Z simply computes Q and then
uses a detrministic Algorithm for satisfiability
problem to determine whether Q is
satisfiable

25. •If O(q(m)) is the time needed to determine
whether formula of length m is satisfiable
then the compexity of Z is O(p
3
(n) logn)+
q(p
3
(n) logn)
•If satisfiability is in P then q(m) is a
polynomial function of m and compexity of
Z becomes O(r(n)) for some polynomial r()
•Hence if satisfiability is in P ,then for every
nondeterministic algorithm A in NP we can
obtain a deterministic Z in P

26. •So It shows that if satisfiability is in P ,then
P=NP