UNIT-V.pdf daa unit material 5 th unit ppt

ppt

1. COURSE: DAAUNIT: 5 Pg: 1
DEPT & SEM :
SUBJECT NAME :
COURSE CODE :
UNIT :
PREPARED BY:
IT & I SEM
DESIGN AND ANALYSIS OF ALGORITHMS
DAA
V
P. LEELA

2. COURSE: DAAUNIT: 5 Pg:
NP –HARD AND NP –COMPLETE PROBLEMS:
NP Hardness
NP Completeness
Consequences of being in P
Cook‘s Theorem
Reduction Source Problems
Reductions: Reductions for some known problems
2
OUTLINE

3. COURSE: DAAUNIT: 5 Pg:
NP –HARD AND NP –COMPLETE PROBLEMS
InComputerScience,manyproblemsaresolvedwheretheobjectiveis
Tomaximizeorminimizesomevalues,whereasinotherproblemswetrytofind
whetherthereisasolutionornot.Hence,theproblemscanbecategorizedas
follows.
OptimizationProblem
Optimization problems are those for which the objective is to maximize or
minimize some values. Forexample,
Finding the minimum number of colors needed to color a given graph. Finding
the shortest path between two vertices in agraph.
DecisionProblem
There are many problems for which the answer is a Yes or a No. These types of
problems are known as decision problems. For example, Whether a given graph
can be colored by only4-colors.
3

4. COURSE: DAAUNIT: 5 Pg:
Finding Hamiltonian cycle in a graph is not a decision problem, whereas checking
a graph is Hamiltonian or not is a decisionproblem.
P-Class
TheclassPconsistsofthoseproblemsthataresolvableinpolynomialtime,i.e.
theseproblemscanbesolvedintimeO(n
k)inworst-case,wherekisconstant.
Theseproblemsarecalledtractable,whileothersarecalledintractableor
superpolynomial.
Formally,analgorithmispolynomialtimealgorithm,ifthereexistsapolynomial
p(n)suchthatthealgorithmcansolveanyinstanceofsizeninatimeO(p(n)).
4
NP –HARD AND NP –COMPLETE PROBLEMS

5. COURSE: DAAUNIT: 5 Pg:
NP-Class
TheclassNPconsistsofthoseproblemsthatareverifiableinpolynomialtime.NP
istheclassofdecisionproblemsforwhichitiseasytocheckthecorrectnessofa
claimedanswer,withtheaidofalittleextrainformation.Hence,wearen’tasking
forawaytofindasolution,butonlytoverifythatanallegedsolutionreallyis
correct.
Everyprobleminthisclasscanbesolvedinexponentialtimeusing
exhaustivesearch.
PversusNP
Everydecisionproblemthatissolvablebyadeterministicpolynomialtime
algorithmisalsosolvablebyapolynomialtimenon-deterministicalgorithm.
AllproblemsinPcanbesolvedwithpolynomialtimealgorithms,whereasall
problemsinNP-Pareintractable.
5
NP –HARD AND NP –COMPLETE PROBLEMS

6. COURSE: DAAUNIT: 5 Pg:
NON-DETERMINISTICALGORITHMS
6
Aswehaveseen,astatespaceisausefulabstractioninanalyzingproblems.
Thevalueoftheabstractionisthatitprovidesaparticularkindofmodularization:
Onecanconsiderseparatelythespacetobesearchedandthealgorithmusedto
searchit.
However,asalgorithmsbecomecomplex,thelanguageofstatesandoperators
quicklybecomestooinexpressiveandawkward.
Whatisneededisarepresentationthatcombinestheabstractionofastate
spacewiththeexpressivityofaproceduralprogramminglanguage.
Thisisachievedinthenotionofanon-deterministicalgorithm.
Thelanguageofnon-deterministicalgorithmsconsistsofsixreserved
words:choose,pick,fail,succeed,either/or.Thesearedefinedasfollows:
chooseXsatisfyingP(X).

7. COURSE: DAAUNIT: 5 Pg:
ConsideralternativelyallpossiblevaluesofXthatsatisfyP(X),andproceedinthe
code.Onecanimaginethecodeasforkingatthispoint,withaseparatethread
foreachpossiblevalueofX.Ifanyofthethreadssucceed,thenthechoice
succeeds.IfachooseoperatorinthreadTgeneratessubthreadsT1...Tk,thenT
succeedsjustifatleastoneofT1...Tksucceeds.
IfthreadTreachesthestatement"chooseXsatisfyingP(X)"andthereisnoXthat
satisfiedP(X),thenTfails.
pickXsatisfyingP(X).FindanyvalueVthatsatisfiesP(V)andassignX:=V.
Thisdoesnotcreateabranchingthreads.
7
NON-DETERMINISTICALGORITHMS

8. COURSE: DAAUNIT: 5 Pg:
failThecurrentthreadfails.
succeedThecurrentthreadsucceedsandterminates.
eitherS1orS2orS3...orSk.Analogoustochoose.CreatekthreadsT1...Tk
wherethreadTiexecutesstatementSiandcontinues.
Someexamples
Generalcommentonpseudo-code:IuseacombinationofthenotationsI
likeinPascal,C,andAda,togetherwithEnglish.Ihopeit'sclearenough.
Inparticular,thelabellingofprocedureparametersas"in","out",and
"in/out"istakenfromAda.FollowingPascal,assignmentisnotated:=and
equalityisnotated=.IdeclarevariablesonlywhenIfeellikeit.
8
NON-DETERMINISTICALGORITHMS

9. COURSE: DAAUNIT: 5 Pg:
THE CLASSES NP -HARD AND NP COMPLETE
If an NP-hard problem can be solved in polynomial time, then all NP-complete
problems can be solved in polynomialtime
All NP-complete problems are NP-hard, but all NP-hard problemsare notNP-
complete.
The class of NP-hard problems is very rich in the sense that itcontains
Many problems from a wide variety ofdisciplines.
9

10. COURSE: DAAUNIT: 5 Pg:
P: The class of problems which can be solved by adeterministicpolynomial
algorithm.
NP: The class of decision problem which can be solved by a non-deterministic
polynomialalgorithm.
NP-hard: The class of problems to which every NP problemreduces
NP-complete (NPC): the class of problems which are NP-hard and belong to NP.
NP-Competence
How we would you define NP
Complete They are the “hardest” problems inNP
10
THE CLASSES NP -HARD AND NP COMPLETE

11. COURSE: DAAUNIT: 5 Pg:
Nondeterministicalgorithms:
A non deterministic algorithm consists of Phase 1:Guessing and Phase 2:Checking.
If the checking stage of a non deterministic algorithm is of polynomial time-
complexity, then this algorithm is called an NP (nondeterministic polynomial)
algorithm.
NP problems : (must be decisionproblems)
–e.g. searching, MSTSorting
Satisfy ability problem (SAT) travelling salesperson problem (TSP) Example of a
non-deterministic algorithms
11
THE CLASSES NP -HARD AND NP COMPLETE

12. COURSE: DAAUNIT: 5 Pg:
Deterministicalgorithm
// The problem is to search for an element x//
// Output j such that A(j) =x; or j=0 if x is not in A
// j choice (1 :n ) if A(j) =x then print(j) ;
success endifprint (‘0’) ;
Failure
complexity0(1);
Non-deterministic decision algorithms generate a zero or one as their output.
Deterministic search algorithm complexity isn.
12
THE CLASSES NP -HARD AND NP COMPLETE

13. COURSE: DAAUNIT: 5 Pg:
SATISFIABILITY:
Letx1, x2, x3…. xndenotes Boolean variables.
Let xi denotes the relation ofxi.
A literal is either a variable or itsnegation.
A formula in the prepositional calculus is an expression that can beconstructed
using literals and the operators and ^ orv.
A clause is a formula with at least one positiveliteral.
The satisfy ability problem is to determine if a formula is true for some
assignment of truth values to thevariables.
It is easy to obtain a polynomial time non determination algorithm that
terminates s successfully if and only if a given prepositional formula E(x1,
x2……xn) issatiable.
13
THE CLASSES NP -HARD AND NP COMPLETE

14. COURSE: DAAUNIT: 5 Pg:
Suchanalgorithmcouldproceedbysimplychoosing(nondeterministically)oneof
the2npossibleassignmentsoftruthvaluesto(x1,x2…xn)andverifythat
E(x1,x2…xn)istrueforthatassignment.
THE SATISFYABILITYPROBLEM:
Thelogicalformula:x1vx2vx3&-x1&-x2
Theassignment:x1←F,x2←F,x3←Twillmaketheaboveformulatrue.
(-x1,-x2,x3)representsx1←F,x2←F,x3←T
Ifthereisatleastoneassignmentwhichsatisfiesaformula,thenwesaythatthis
formulaissatisfiable;otherwise,itisunsatisfiable.
Anunsatisfiableformula:x1vx2&x1v-x2&-x1vx2&-x1v-x2
14
THE CLASSES NP -HARD AND NP COMPLETE

15. COURSE: DAAUNIT: 5 Pg:
THE SATISFYABILITYPROBLEM
The logical formula:
x1v x2 v x3 & -x1 &-x2
the assignment : x1 ← F , x2 ← F , x3 ← T will make theabove formula
true . (-x1, -x2, x3) represents x1 ← F, x2 ← F, x3 ←T
If there is at least one assignment which satisfies a formula, thenwe
say that this formula is satisfiable; otherwise, it is un satisfiable. An un
satisfiableformula:
x1vx2 &x1v-x2 &-x1vx2&-x1v-x2
15
THE CLASSES NP -HARD AND NP COMPLETE

16. COURSE: DAAUNIT: 5 Pg:
SOME NP-HARD GRAPHPROBLEMS
The strategy to show that a problem L2 is NP-hardis
Pick a problem L1 already known to beNP-hard.
Show how to obtain an instance I1 of L2m from any instance I of L1 such that
from the solution of I1 We can determine (in polynomial deterministic time)
thesolutiontoinstanceIofL1
Conclude from (ii) thatL1L2.
Conclude from (1),(2), and the transitivity of that Satisfiability L1 L1L2
Satisfiability L2 L2isNP-hard
16
THE CLASSES NP -HARD AND NP COMPLETE

17. COURSE: DAAUNIT: 5 Pg:
CHROMATIC NUMBER DECISION PROBLEM(CNP)
A coloring of a graph G = (V,E) is a function f : V □{ 1,2, …, k} i V If (U, V)
E then f(u)f(v).
The CNP is to determine if G has a coloring for a givenK.
Satisfiability with at most three literals per clause chromatic number problem.
CNP isNP-hard.
DIRECTED HAMILTONIANCYCLE(DHC)
Let G=(V,E) be a directed graph and length n=1V1 The DHC is a cycle that goes
through every vertex exactly once and then returns to the starting vertex.
The DHC problem is to determine if G has a directed Hamiltonian Cycle.
Theorem: CNF (Conjunctive Normal Form) satisfiability DHC DHCis NP-hard.
17
NP HARDPROBLEMS

18. COURSE: DAAUNIT: 5 Pg:
COOK'STHEOREM
StephenCookpresentedfourtheoremsinhispaper“TheComplexityofTheorem
ProvingProcedures”.Thesetheoremsarestatedbelow.Wedounderstandthat
manyunknowntermsarebeingusedinthischapter,butwedon’thaveanyscope
todiscusseverythingindetail.
FollowingarethefourtheoremsbyStephenCook−
Theorem-1
IfasetSofstringsisacceptedbysomenon-deterministicTuringmachinewithin
polynomialtime,thenSisP-reducibleto{DNFtautologies}.
18

19. COURSE: DAAUNIT: 5 Pg:
COOK'STHEOREM
Theorem-2
ThefollowingsetsareP-reducibletoeachotherinpairs(andhenceeachhasthe
samepolynomialdegreeofdifficulty):{tautologies},{DNFtautologies},D3,{sub-graph
pairs}.
Theorem-3
ForanyT
Q(k)oftypeQ,TQ(k)k√(logk)2TQ(k)k(logk)2isunboundedThereisaT
Q(k)
oftypeQsuchthatTQ(k)⩽2k(logk)2TQ(k)⩽2k(logk)2
Theorem-4
IfthesetSofstringsisacceptedbyanon-deterministicmachinewithintimeT(n)=
2
n
,andifT
Q(k)isanhonest(i.e.real-timecountable)functionoftypeQ,thenthereisa
constantK,soScanberecognizedbyadeterministicmachinewithintimeT
Q(K8
n
).
19

20. COURSE: DAAUNIT: 5 Pg:
COOK'STHEOREM
COOK’STHEOREM
Cook’sTheoremstatesthatAnyNPproblemcanbeconvertedtoSATinpolynomial
time.
Inordertoprovethis,werequireauniformwayofrepresentingNPproblems.
RememberthatwhatmakesaproblemNPistheexistenceofapolynomial-time
algorithm—morespecifically,aTuringmachine—forcheckingcandidatecertificates.
WhatCookdidwassomewhatanalogoustowhatTuringdidwhenheshowedthatthe
EntscheidungsproblemwasequivalenttotheHaltingProblem.
HeshowedhowtoencodeasPropositionalCalculusclausesboththerelevantfacts
abouttheprobleminstanceandtheTuringmachinewhichdoesthecertificate-
checking,insuchawaythattheresultingsetofclausesissatisfiableifandonlyifthe
originalprobleminstanceispositive.
Thustheproblemofdeterminingthelatterisreducedtotheproblemofdetermining
theformer.
20

21. COURSE: DAAUNIT: 5 Pg:
COOK'STHEOREM
LetusassumethatMhasqstatesnumbered0,1,2,...,q1,andatapealphabeta
1,
a
2,...,a
s.Weshallassumethattheoperationofthemachineisgovernedbythe
functionsT,U,andDasdescribedinthechapterontheEntscheidungsproblem.
Weshallfurtherassumethattheinitialtapeisinscribedwiththeprobleminstance
onthesquares1,2,3,
...,n,andtheputativecertificateonthesquaresm,...,2,1.Squarezerocanbe
assumedtocontainadesignatedseparatorsymbol.
Weshallalsoassumethatthemachinehaltsscanningsquare0,andthatthesymbol
inthissquareatthatstagewillbea
1ifandonlyifthecandidatecertificateisatrue
certificate.
NotethatwemusthavemP(n).Thisisbecausewithaprobleminstanceoflengthn
thecomputationiscompletedinatmostP(n)steps;duringthisprocess,theTuring
machineheadcannotmovemorethanP(n)stepstotheleftofitsstartingpoint.
21

22. COURSE: DAAUNIT: 5 Pg:
COOK'STHEOREM
Wedefinesomeatomicpropositionswiththeirintended
interpretationsasfollows:
For i = 0, 1, . . . , P (n) and j = 0, 1, . . . , q 1, the proposition Q
ijsaysthat
after i computation steps, M is in statej.
For i = 0, 1, . . . , P (n), j = −P (n), . . . , P (n), and k = 1, 2, . . . , s,the
proposition S
ijksays that after i computation steps, square j ofthe
tape contains the symbola
k.
i = 0, 1, . . . , P (n) andj=P (n), . . . , P (n), the proposition T
ijsays that after i
computation steps, the machine M is scanning square j of thetape.
22

23. COURSE: DAAUNIT: 5 Pg:
REDUCTIONSFORSOMEKNOWNPROBLEMS
23
THECLIQUEPROBLEM:
Cliques:
SupposethatGisanundirectedgraph.SaythatasetSofverticesofGformacliqueif
eachvertexinSisadjacenttoeachothervertexinS.
TheCliqueProblem
Thecliqueproblemisasfollows.
Input.AnundirectedgraphGandapositiveintegerK.
Question.DoesGhaveacliqueofsizeatleastK?
Let'slookatthesameexamplegraphthatwasusedearlierfortheVertexCover
andIndependentSetproblems,whereG
1hasvertices
{1,2,3,4,5,6,7,8,9}anditsedgesare{1,2},{1,4},{1,6},{1,8},{2,3},{3,4},{4,5},
5,6},{6,7},{7,8},{8,9},{2,9}.
Wesawthat{2,4,6,8}isanindependentsetinG
1,whichmeansthat{2,4,6,8}is
acliqueinG
1.ButwhataboutacliqueinG
1?

24. COURSE: DAAUNIT: 5 Pg:
CLIQUE DECISIONPROBLEM
A largest clique in G
1 is {1,2}, having just twovertices.
But look at graph G
2 with vertices {1, 2, 3, 4, 5, 6, 7, 8} andedges
{1, 2},{1,6},
{1, 7},{1,8},
{2, 3},{2,5},
{2, 6},{3,5},
{3, 6},{4,5},
{4, 6},{5,6}, {7,8}.
Does G
2 have a clique of size 3? Yes: {1, 7, 8}. But what about a cliqueof size4?
24

25. COURSE: DAAUNIT: 5 Pg:
CLIQUE DECISIONPROBLEM
An idea for finding largecliques
Here is an idea for finding a largeclique.
The degree of a vertex v is the number of edges that are connected tov.
To find a clique ofG:
Suppose that G has nvertices.
Find a vertex v of the smallest possible degree inG.
If the degree of v is n − 1, stop; G is a clique, so the largestclique in G has sizen.
Otherwise, remove v and all of its edges from G. Find the largest clique in the smaller
graph. Report that as the largest clique inG.
25

26. COURSE: DAAUNIT: 5 Pg:
THE CHROMATIC NUMBER DECISION PROBLEM
The chromatic number decision problemis defined asfollows:
We are given a graph G = (V, E). For each vertex, relate it with a color in such a way
that if two vertices are connected by an edge, then these two vertices must be
related with different colors.
The chromatic number decision problem is to find the least possible number of
colors to color the vertices of the givengraph.
Types of Graphs with their respective chromatic numbers:
Cycle Graph:Examples
26

27. COURSE: DAAUNIT: 5 Pg:
THE CHROMATIC NUMBER DECISION PROBLEM
Cycle Graph Chromatic Number: 2 colors if number of vertices is even 3 colors if
number of vertices isodd
PlanarGraph:Inplanar graphs, the edges do not cross (except at a vertex). Planar
graphs are widely used to representmaps.
EXAMPLES:
27
Planar Graph Chromatic Number: Less than or equal to4

28. COURSE: DAAUNIT: 5 Pg:
Complete Graph: In a complete graph, each vertex is connected to every other vertex
by an edge.
EXAMPLES:
Complete Graph Chromatic Number: Equals to the number of vertices of the given
completegraph.
28
THE CHROMATIC NUMBER DECISION PROBLEM

29. COURSE: DAAUNIT: 5 Pg:
DIGITAL RESOURCES
29
Lecture Notes -Lecture Notes
VideoLectures -Video Lecture
E-Book -Design and Analysisof AlgorithmsConcepts
Model Papers-JNTUA Question Papers