Limits of
Computation
19 – How Hard is a Problem? Bernhard Reus
1
The story so far
• we have seen NP contains problems that seem intractable
• we don’t know whether P = NP i.e. whether the seemingly intractable problems are actually tractable.
• Today we develop at least an “angle” to attack this problem.
2
We don’t know
NP \ P
but we can look at the
“hard” problems in there!
3
“Hard” Problems in (N)P •THIS TIME
add complexity to problem reduction (of Lecture 9): “if you can solve B then you can solve A as well”. (A is not harder than B) A≤B
• what are the “hardest” problems in (N)P (called complete problems)?
• why they are important?
4
n more interesting: Many natural and practically motivated problems have been v
q e e u
s
e
t v
w
x
e i p
v e
t o
o
h
on 25.1.1
en to be complete for one or another complexity class C. Forms o
of reduction uite early i nt unsolvab
years, for plexity of devised to
f reduction
Reduction
of one problem to another has been studied for many
see Lecture 9, Slides 18ff
n Mathematical Logic as a tool for comparing the com
• to be able to show that problem A is no
le problems or undecidable sets. Many ways have been
harder than problem B, reduce the problem. anothersinceEmilPost’spathbreakingworkinEm1il9Le4on4Pos[t
• many-one reduction from A to B (A≤B) is given
where (say) A, B ID can be defined in several ways.
(1897-1954) ny-ionnpeu:t)odnateashuocwhsthtahtat A⇥B by exhibiting a total co
by a total computable function f on (problem decide membership in A
ranyd⇤IDwehave .C in terms of B using f
d⇤A if and only if f(d)⇤B
g membership in B can be used to decide membership • Many-one as f maps (many values) to one value
be given shortly.) A stronger version is one-one, in and “is in B?” can only be asked once at the end.
e. there are more general forms of reduction truth-table reducibility, where one answers a question x
problemto143].
ction A ⇥ B First, the maybemamputable
uchthatfolearly,an
for decidin xample will o be injectiv
ernative is
eral questions
ers in some preassigned way. Yet another variant is Turing reducibility, where
⇤ A? gives rise to a dialogue: a whole series of questions about membership firstquestndepend andtheresorth.The rement on s for every
wer sequenc
utability is reduction
e.Complexomplexity stions that many-one y.Inorderbility,itis limitone’slgorithms
lynomial in
Three e
Section A.1 describes graphs, and boolean expressions and their evaluation. e term CNF to stand for conjunctive normal form.
y ⇤ B, . . . , y 1k
5
⇤ B?,
⇤ A? by and then combining the truth values of
in A. (A which f is
ion depends only on x. The second question (if any) ca ponse (positive or negative) to the first question; and so f
Very Simple Example • reduce the Travelling Salesman Problem
uch a reduction is that the series is required to terminate
e.
being studied, the only essential requirement is that the
where start = finish city to the Travelling
ity classifications are naturally involve bounds on the c
Saleman Problem with different start and
can be asked, for example of the function f used for
encoding of graph
finish cities.
to study, say, the class nptime using many-one reduci • f([G,K,A]) = [G,K,A,A]
self to questions that can be computed by deterministic a
|x|.
xample problems
encoding of city start=finish encoding of mileage limit
6
Theorem 19.2 (Transitivity of P). If A P B and B P C then A P C.
Proof. From A P B follows that there is an f1 computable by a program r1 in polynomial time (say p1(n)) such that x 2 A iff f1(x) 2 B. From B P C follows that there is an f2 computable by a program r2 in polynomial time (say p2(n)) such
that x 2 B iff f2(x) 2 C. From both follows immediately that x 2 A iff f2( f1(x)) 2 C.
So the reduction function for A P C is the composition of f1 and f2. Clearly this
composition is again computable by first running r1 and then r2. We can now write
aprogramqthatimplementsthecompositionoff andf asoutlinedinFig.19.3. 12
Reduction for Complexity Comparison
• For reduction between problems in a
q read x {
y :=
complexity class, the reduction must be
z :=
w•rite y
… i.e. must be computable (as before) and not
carry out of the complexity class at hand.
Fig. 19.3: Program q that computes f2( f1(x)) in WHILE-syntax • So for NP or P the reduction function f should
R. Karp
It remains to check that q runs in polynomial time. We can calculate be computable in polynomial time.
• we write A≤ B
We don’t know exactly what the size of f1(d) will be, but we can give an upper bound for it just like in the proof of the previous theorem and therefore we get that
time (d)=2+(1+p (|d|))+“(p1o+lypno(m|fi(adl)|t)imereduction” qp121
or Karp-reduction
time (d) 2+(1+ p (|d|))+(1+ p (p (|d|))) q1721
and therefore
Now the right hand side is a polynomial again as the addition and the composition
timeq(d) p1(|d|) + p2(p1(|d|)) + 4
of two polynomials gives a polynomial.
Complete Problems
Definition 19.3 (Complete Problem). For any complexity class C a problem H is called complete for the class C if problem H is itself in C and is “hardest” in C in the sense that for all other problems A 2 C we have that A H (for an appropriate instantiation of reduction).
Important feature of NP-2c5o1mplete problems:
To show that P = NP it suffices to show that any one NP-complete problem H is actually in P.
First, we prove closure of N(P) under poly-time reduction:
19.3 Hard Problems
8
otonic and | f (d)| p (W|d|)esikncn
erministic) program r that runs in
is clearly a polynomial time reduction as the reduction function can be implemented 33
sbeenintroducedbyhEamsiblePeonstintarnoduincethdebcyonEtmexitloPfocstomapnudtaitniotnhaelcomntpelxetxoitfycomputationalcomplexity
by a (deterministic) program that runs in constant and thus polynomial time.
ampioned by RichardchKaamrp.ioTnhedrebdyuRcticohnabredtwKeaernp.thTehtewroedvuercstionsboeftwtheeTnStPhe two versions of the TSP
Next we will look at some useful results about polynomial time reduction that we
clearlyapolynomialtiismceleraerdluycatiponolaysntohmeriaedluticmtieonrefduunctioncaasnthberimedpulcemtioentfeudnctioncanbeimplemented
19.2. P-REDUCTION CHAPTER 19. HOW HARD IS A PROBLEM?
a (deCteHrAmPiTnEisRtic1)9.prHoObwgyWraialmHl(AudthResatDeterI–umSniAismnPinsRptOiclcioB)cnLipstEtrlaoMyng?tranmd tehxautsprpluionclsyitnilnoymc–oianilsntiamtnhete.anfdoltlhouws pinolgy.nTomheiayl taimre.very much related to
Next we will look at somNeeuxstewfuelwreislulltosoakboauttsopomlyenuosmefiualtriemsuelrtesdaubcotiuotnptohlaytnwoemial time reduction that we
Thm. 9.4 that helped us deduce (un-)decidability results with the help of “effective”
l use – implicitly andweixllpulisceit–lyi–mipnlitchietlfyolalnowdienxgp.lTichietlya–reinvethryemfoulclohwreinlagte.dThtoey are very much related to
reduc
decidable problems. of decidable problems.
Dibility . We can now prove an analogous result to Thm 9.4 about , but
p read xc {
rec rec m. 9.4 that helped usTdhemdu.c9e.4(utnh-a)tdehceildpaebdiluitsydresdulctsew(uitnh-)thdechiedlapboilfit“yefrfescutilvtse”with the help of “effective”
x := hd xc;
now we use with polynomial time reduction and NP (or P) instead of the class
of decidable problems.
w we use with polynnoomwialwteimueserewduitchtiopnolynoamnidalNtPim(oerrPed)uinctsitoenadof tahnedcNlasPs (or P) instead of the class
c := hd tl xc;
P
ucibility . We carnednuocwibpirliotvyean a.nWaloegcoauns nreoswultptrovTehamn9a.n4aalbooguotus res,ubluttto Thm 9.4 about , but rec B rec rec rec
ownward-closure (N)P }wri P
te y
P
Theorem 19.1 (Downward closure of (N)P). If A P B and B is in NP then A is
eorem 19.1 (Downward closure of (N)P). If A B and B is in NP then A is
Theorem 19.1 (Downward cPlosure of (N)P). If A B and B is in NP then A is
Fig. 19.1: Verifier p showing B 2 NP P19.2. P-REDUCTION CHAPTER 19. HO alsoinNP.Similarly,IfA BandBisinPthenAisalsoinP.
9.1: Verifier p showing B 2 NP P oinNP.Similarly,IfA BandBisinPthenAisalsoinP.
alsoiPnNP.Similarly,IfAP BandBisinPthenAisalsoinP.
Pproolyonof.miaWltiemefi,rsasytpsh(no)w,sutchithsatfox2rNAiPff.fS(x)o2aBs.sWuemthereAforedefiBneathnedBisinNP.Fromthelatter oof. We first show this for NP. So assume1A B and B is in NP. From the latter P
Proof. WefirstshowthisPforNP.SoassumeAPBandpBriseaindNxcP.{Fromthelatter such that x 2 A iff f (x) 2 B. We therefore define the
program q as given in in Fig. 19.2 where the macro call
itffoolllolwowstshatthtahterteheisreapisolaynpoomliyalntoimeiavlertifimerepvfeorrifiBe.rWpehfaovreBto.cWonesthruacvteatoconstructa 19.2 where the macro call
ynomial time verifier for A, let’s call that one q. If we could achieve that
polynomial time verifier for A, let’s call that one q. If we could achieve that
n we’d know that
verifier for B
the}n we’d know that Fig. 19.1: Verifier p showing B
run p on input f(x)
polynomial time verifier for A, let’s call that one Bq. If we could achieve that
} JqK(x,c)=JpK(f(x),c) (†) write y
q read xc {
x := hd xc;
c := hd tl xc;
JqK(x,c) = JpK(f(x),c) (†)
x :=
then we’d know that
x := f(x) B // run p on input f(x)
JqK(x,c)=trueforacertificatec iffJpK(f(x),c)=trueforacertificatec wJrqiKte(xy,c)=trueforacertificatec iffJpK(f(x),c)=trueforacertificatec
JqK(x,c) = JpK(f(x),c) (†)
iff f(x)2B
veJrqifiKe(rxf,ocr)A=trueforacertificatec iffJpK(f(x),c)=trueforacertificatec
iff x 2 A
iff f(x)2B
iff x 2 A polynomial time, say p (n), such that x 2 A iff f(x)
Fig. 19.2: Program q made from bits of pifafndfr(x) 2 B
rogram q made from bits of p and r tethatthelaststepisaconsequencefromthefactthatA B.Wethusknowthat
P iff x 2 A
Note that the last step is a consequence from the fact that A P B. We thus know that
s a verifier for A. But how do we define q and why is it polynomial in the size of
new program q fulfils condition (†) by construction. It remains to show that q runs
q is a verifier for A. But how do we defin9e q and why is it polynomial in the size of
in polynomial time. We have that
First of all we assume that all verifiers and other programs are given in WHILE.
xN?oFtiersthoaftatlhlweelaastsusmteepthisataacllovnesriefiqeurseanncdeoftrhoemrprtohgerafmacstatrheagtivAeninWBH.IWLeE.thusknowthat q read xc { P
on (†) by construction. It remains to show that q runs
that
is is not a limitation due to Cook’s thesis discussed in Chap. 14. Let us assume
This is nottimael(idm,cit)a=tio2n+d3u+e4t+o“Ctimoeofko’rsxt:h=e
q is a verifier for A. But how do we define q and why is it polynomial in the size of t p looks like given inFigure 19.1 and has polynomial time bound, say p (n). c := hd tl xc;
that p looks like given inFig1ure 19.12 and has polynomial time bound, say p (n). 3+4+“timeforx:=
2 x?Firstofallweassumethatallverifiersandothxe:r=p
10+ p (|d|)+ p (p (|d|)) knowthatfunctionfiscomputableby(determ1inistic)2pr1ogramrthatrunsin
1 + p1(|d|)) + p2(| f (d)W|) e know that function f is computable by (deterministic) program r that runs in
B // run p on input f(x
p1(|d|)+p2(p1(|d|)) ThisisnotalimitationduetoCook’sthesisdiscussedinChap.14.Letusassume
1
program q as given in in Fig. 19.2 where the macro ca
We have used in the last inequality that p (| f (d)|) p (p (|d|)) which follows 221
here are other variations2 of reduction where e.g. the question “is in B?” can be asked several
There are other variations of reduction where e.g. the question “wirsinteB?y” can be asked several
thfraomttphelfoacotkthsatlpikiesmgoinvoteoniciandF|ifg(du)r|e1p9(|.d1|)saincdetheassizepooflthyenooutm-ialtimebound,sayp(n).
sr,vSaur polynomial in n which follows from the fact that the
erds
2o0n
isCionmBp?u”tactainonbe asked several tosno“f
mial.
times.
ials is a polynomial again, so p (p (n)) is a polyno-
1w7
250
JqK (x, c) = true for a certificate c
Note thaastrtehqeuliarsetds.tep is a consequence from the fact that A B. We thus
eotwhe s
tes f cannot be larger than the time it takes to run p
o famous for his “Post System” that can be used as a model of computation.
tihzeao
tf fthuen
arde Downward-closure
10 + p (n) + p (p (n)) is a polynomial in n which follows from the fact that the also fam1ous for2his1“Post System” that can be used as a model of computation.
we know that q has a polynomial time bound since
composition of two polynomials is a polynomial again, so p (p (n)) is a polyno-
Fig. 19.2: Program q made from bit
c2 BTehrenreh
oRtehue
isastei
h
oxnUsno ifvre
uitcyti
ere 2
21 249
For the second statement the proof is analogous as the composition of the deter-
om
uta
le
c BeEarnmndihlprLao.drPudocesRtt(hFeiseubosruu,tpaSurytu1.s1Ss,oe1wx89e7Uk–nnoAwivptrehilart2s1qit,hy1a9s52a40)p1wol7aysnoamniAalmtiemriecabnoumnadthsLienmicmeatiictiasnoanfdCloogmiciapnu,tation
249
to co3nstruct a polynomial time verifier for A, letn’eswcparollgrtahmaqtfuolnfiels cqo.ndIiftiowne(†c)obuylcdonstruction. I
then we’d know that
250
i↵ JpK (f (x), c) = true for a certificate c
We have used in the last inequality that p2(|f(d)|)
by
(d
e.g1
mEimnisitlicLp.roPgorasmts(Fpeabndrurainryth1is1c,as1e8g9iv7es–asAapdreitler2m1in,i1st9ic5q4.) was an American mathematician and logician,
so we have now a program q such thinaptolynomial time. We have that he proof is analogous as the composition of the deter-
achieve that toalcsonfsatmruocutsafoprohliysn“oPmoisatlStyismtemv”erthifiaetrcafonrbAe,usletd’sascallmtohdaetlonfecoqm.pIuftwateiocno.uld
4 This follows from the definition of time measures as the construction of large expressions is
timeq(d,c) = 2+3+4+“time for x:=
B
} writ
new pro in polyn
// x := f(x)
// run p on input f(x)
}
write y
have that Wehaveollows
9+(1+ p1(|d|))+ p2 fromtheheout-
put of p run p
st inequality that p2(|
andproddsince
10 + p (n) + p (p (n)) is a polynomial in n which follows from the fact that the
121 compositionoftwopolynomialsisapolynomialagain,sop10(+pp(n))+)pi(spa(n)p)oislaypnooly-nomialinn
mial.
211 21
composition of two polynomials is a polynom mial.
11
and produce this output4. So we know that q
For the second statement the proof is analo For the second statement the proof is analogous as the composition of the deter-
ministic programs p and r in this case gives as a deterministic q. 4asure.Foreachtimeunitc
Thisfosionsis accountedne“bit” of the out
250
If P is not equal to NP, then by Ladner’s Theorem [7] there must be also at least 12
one problem that is in NP but that is not NP-complete nor in P. These problems are called NP-intermediate problems We omit the details here but point out that the proof constructs a problem by diagonalisation that is quite unnatural. There are some more natural candidates for such intermediate problems which will be discussed in
Fig. 19.1: Verifier p sho (n), such that x2A i
Fig. 19.2 where the m
ey
Fig. 19.2: Program q made from bits of p and r Remains to check runtime
Assume program r runs in polynomial time p1(n) gram q fulfils condition (†) by construction. It remain
Assume program p runs in polynomial time p2(n) omial time. We have that
timeq(d,c) = 2+3+4+“time for x:=
= 9+(1+p1(|d|))+p2(|f(d)|) 10 + p1(|d|) + p2(p1(|d|))
*|d|
the last inequality that p (| f (d)|) p (p (|d|)) which f
u fatp2ismonotonicand|f(d)|p1(|d|)sincethesizeoft
sed in ct tha
polynomial time, say p1 program q as given in in
new program q fulfils c in polynomial time. We
2 2 1 timeq(d,c)= |f(d)| ≤ p1(|d|)*|d| why? =
by inspecting how large a tree can be produced
rogram p that computes f cannot be larger than the time it takes to 4 so q runs in polynWoemhiaavle utsiemd ein the la
uce this output . So we know that q has a polynomial time boun from the fact that p2 is
q read xc {
x := hd xc;
c := hd tl xc;
s to show that
B }
body of p
x :=
write y
monotonic and |f(d)| put of program p that computes f cannot be l
ministic programs p and r in this case gives as
q runs
// run p on inp
// x := f(x)
9.2: Program q made f ondition (†) by constru
2+3+4+“time for
10 + p1(|d|) + p2(p1(
4 This follows from the de CHAPTER19. HOWHARDISAPROBLEM? 19.3. HARaccDounPteRdOforBinLthEeMtimSeme
of the output
llows from the definition of time measures as the construction of large expres
for in the time measure. For each time unit consumed one can at most produce o With the help of NP-complete problems we can show a very useful result that char-
Why complete problems?
put
acterises the big problem we have in not knowing whether P= NP. It provides us
with an “angle” to attack this big open problem:
Theorem 19.4. If any NP-complete problem is already in P then P = NP (and the 250
biggest open problem in theoretical computer science is solved).
Proof. LetHbetheNP-completeproblemthat,byassumption,isalsoinP.Weonly
have to show that NP ✓ P since we know that P ✓ NP holds anyway (see previous
chapter) and from both we immediately can infer that P = NP.8 To show NP ✓ P we Proof: Let H be the NP-complete problem that is in P.
take any problem A 2 NP and show that A 2 P holds as well (using the assumptions We only have to show that NP ⊆ P as the other direction
we have about H; of course this does not hold in general!). H is NP-complete and
Ah2oNldPsmaenaynws bay.d
efinition of NP-completeness that A P H. We now know also
that H is in P. By the “Downward-closure of P” Thm. 19.1 we can conclude that We’ll give details on the next slide.
A2P.
We don’t know yet whether P = NP and therefore we have two possible scenarios as highlighted in Fig. 19.4 which shows the two cases. Recall that R from Def. 9.2 defines the class of decidable problems.
finition of time measures
WHARDCISHAPTREORBL1E9.MH?OWHA19R.D3.IHSARPDRPORBOLBELME?MS 19.3. HARDPROBLEMS
CHAPTER 19. HOW HARD IS A PROBLEM? 19.3. HARD CHAPTER 19. HOW HARD IS A PROBLEM? 19.3. HARD
CHAPTER 19. HOW HARD IS A PROBLEM? 19.3. HARD PROBLEM
complete problems we can show a very useful result that char-
With the help of NP-complete problems we can show a very useful result that char-
With the help of NCPH-cAoPmTpElRete19p.roHbOleWmsHwAeRcDanISshAoPwRaOvBeLryEMus?eful re With the help of NP-complete problems we can show a very useful res
blem we have in not knowing whether P= NP. It provides us
acterises the big problaecmterwiseshtahveebiingnporotbklneomwwineghwavhetihnenroPt=knNoPw.inIgt pwrohvetihdersPu=s NP.
With the help of NP-complete problems we can show a very useful result that cha acterises the big problem we have in not knowing whether P= NP. I
ack this big open problem: withan“angle”toattackthisbigopenpWroitbhlethme:helpofNP-completeproblemswecanshowa
with an “angle” to attack this big open problem:
acterises the big problem we have in not knowing whether P= NP. It provides u
with an “angle” to attack this big open problem:
with an “angle” to attack thaicstberigiseospethnepbroigblpermo:blem we have in not knowing wh
y NP-complete problem is already in P then P = NP (and the
Theorem 19.4. If any NP-complete problem is already in P then P =
Proof
Theorem 19.4. If any NP-complete problem is already in P then P = NP (and the
with an “angle” to attack this big open problem:
Theorem 19.4. If any NP-complete problem is already in P then P = in theoretical computer science is solved).
biggest open problem in theoretical computer science is solved). Theorem 19.4. If any NP-complete problem is already in P then P = NP (and th
biggest open problem in theoretical computer science is solved).
biggest open problem in theoretical computer science is solved).
biggestopenproblemintheTohretoirceamlc1o9m.p4u.tIefrasncyieNnPce-ciosmsopllveeted)p.roblemisalready
NP-complete problem that, by assumption, is also in P. We only
Proof. LetHbetheNP-completeproblemthat,byassumption,isalso
biggest open problem in theoretical computer science i Proof. LetHbetheNP-completeproblemthat,byassumption,isalsoinP.Weonly
✓ P since we know that P ✓ NP holds anyway (see previous
Proof. LetHbetheNP-completeproblemthat,byassumption,isalso
have to show that NP ✓ P since we know that P ✓ NP holds anyway Proof. LetHbetheNP-completeproblemthat,byassumption,isalsoinP.Weon
have to show that NP ✓ P since we know that P ✓ NP holds anyway (see previous hweimmediatelycaninferthatP=NP.8 ToshowNP✓Pwe 8
have tocshhaopwtert)haantdNfrPom✓bPothsiwnceeimwmeekdniaotwelythcant Pinf✓er NthPat Pho=ldNsPa.nyTwo ashyo have to show that NP ✓ P Psirnocoef.wLeektnHowbeththaet PNP✓-cNoPmphloeltdesparnoybwleamyt(hsaete, bpyreavsisou
chapter) and from both we immediately can infer that P = NP.8 To show NP ✓ P8we NP and show that A 2 P holds as well (using the assumptions 8
chaptterr)t)aankdnedfarnofyrmopmbrotbhloewtmhe iwAhmae2vmeieNmtdoPimastahenoldydwiacstahthenoalwtiynNfctePharan✓thAiaPnt2fPseiPrn=ctNhehoaPwlt.dePsTkano=sosNwhoePtwlhl.a(NtuTPsoi✓nsghPNtohPw course thtiaskdeoaensynportohbolledminAg2enNerPala!n).dHshioswNtPh-actoAm2plePtehoanlds as well (using the assumptions
takeanywperohbalevmeaAb2ouNtPHa;cnohdfaspchtoeourw)rsatenhdathtfAirso2mdoPbeoshtohnlodwtsehaisomlwdmeeilnld(igauteseinlnyegrcatahl!ne).ianHsfseurimsthpNattiPoP-n take any problem A 2 NP and show that A 2 P holds as well (using the
finition of NP-completeness that A H. We now know also
we have about H; of coursePthis does not hold in general!). H is NP-complete and
we haveAab2ouNtPHm; oefancosubrysetadktehefiisanndiytoioepsnronoboflteNmhoPAl-dc2oinmNgPpelneaenterdanlse!h)s.oswHthtiahstaNtAAP-2coPmHhp.olWeldteseansn
P
we have about H; of course this does not hold in general!). H is NP-c
e “Downward-closure of P” Thm. 19.1 we can conclude that
A 2 NP means by definition of NP-completeness that A H. We now know also
A 2 NPtmhaetanHs bisyidnefiPn.iBtioywntehoefhaN“vDPe-oacwboomnuwptlaHertd;e-noceflsocPssotuhraesteoAtfhiPs”dHoTe.hsWmne.ot1nh9oo.w1ldkwineowgceananles
P
A 2 NP means by definition of NP-completeness that A H. We no
P
that H is in P.tBhayt HtheiAs“i2DnoPw. Bnwyathrde-“cDloosAwun2rewNaorPfd-Pmc”leoaTsnuhsrmebyo.fd1Pe9fi”.1nTitwhiomen.co1af9nN.1cPow-nceocmcluapdnlectoethnacelstusdtehatth
A2P.
that H is in P. By the “Downward-closure of P” Thm. 19.1 we can c A 2 P. that H is in P. By the “Downward-closure of P” Thm
whether P = NP and theAre2forPe.we have two possible scenarios
We don’t know yet whether P = NP and therefore we have two poss
A2P.
19.4 which shows the two cases. Recall that R from Def. 9.2
Wedaosn’htikgnholwighyteetdwihnetFhiegr.P19=.4NPwhanicdhthsehroewfosrethweethwaovectawseosp.oRsesicballelstcheantaRrio We don’t know yet whether P = NP and therefore we have two possible scenarios
We don’t know yet whether P = NP and therefore we have two possi as highlighted in Fig. 19.4 whWiche dshoonw’tsknthoewtwyeot cwahsetsh.eRrePca=llNthPaatnRd fthroemrefDoref.w9e
ecidable problems.
as highlighted in Fig. 19.4 which shows the two cases. Recall that R from Def. 9.2
defines the class of decidable problems.
as highlighted in Fig. 19.4 which shows the two cases. Recall that R f NP, then by Ladner’s Theorem [7] there must be also at least
defines the class of decidabalse hpirgohbliegmhtse.d in Fig. 19.4 which shows the two cases. If P is not equal to NP, then by Ladner’s Theorem [7] there must b
defines the class of decidable problems.
n NP but that is not NPd-ecfionmepslethteencolrasisnoPf.dTehceisdeabplreobplreombslems.
If P is not equal to NP, tdheefinnbeys tLhaedcnlears’ssoTfhdeeocriedmab[l7e]ptrhoebrlemsu.st be also at lea
one problem that is in NP but that is not NP-complete nor in P. Th If P is not equal to NP, then by Ladner’s Theorem [7] there must be also at least
13
ediate problems We omit the details here but point out that the oneIfprPobilsemnotheatquisailntoNPNPbu,ItfthtPheaintsinbsoyntoLetqauNdaPnl-etcoro’NsmPTp,lhethteonreobmryiLn[a7Pd]n.teThrh’eserTseehmeporuoresbmtlebm[
are called NP-intermediate problems We omit the details here but poi one problem that is in NP but that is not NP-complete nor in P. These problems
blem by diagonalisation athreatciasllqeudiNtePu-nintaetrumreadl.iaTtheeprreobarlemsosmWe omit the details here but point out that th one problem that is in NP but that is not NP-comple
one propbroleomf cothnastruisctisna NprPoblbeumt bthyadtiaigsonoatlisNatPio-ncothmatpilseqteuinteourninatPur.aTl.hT
are called NP-intermediate problems We omit the details here but point out that the
tes for such intermediateprporofbcleomnsstrwuchtsicahpwroibllebme bdyisdciuagssoendalinsation that is quite unnatural. There are som
are called NP-intermediate problems We omit the deta more natural candidates for such intermediate problems which will b
are called NP-intermediate problems We omit the details here but poin proofconstructmsaorpernoabtluermalbcayndiadgaotensafloisrastuiochnitnhtaetrmiseqduiaitepurnonbaletumrsalw.Thihcehrweiallrebesodmisecussed
proof constructs a problem by diagonalisation that is qu proof constructs a problem by diagonalisation that is quite unnatural. Th
Sect. 20.6.
erestingresultsthatindiScaetcet.t2h0a.t6“.standardtechnimquorees”nawtuorna’ltcandidatesforsuchintermediateproblem more natural candidates for such intermediate problems which will be discussed in
There are other interesting results that indicate that “standard tech more natural candidates for such intermediate problems which will be
er P = NP. We won’t go inTthoerdeeatraeilostherein,tberuetstihSnegcirtne.ts2eu0rle.t6s.tehdat indicate that “standard techniques” won Sect. 20.6. work to prove whether P = NP. We won’t go into details here, but
s chapter.
puzzlEexseracisesproblems and confirm that some famous ones are “hard” in the form hardproblemviareductihoanta.lWltheeaprreobmleaminsloyfiCnhteapre.s1t7eadreinNtPh-ecocmlapslseteNaPn,d
Sect. 20.6.
relativized classes” wherweoprkrotgorapmrosve(owrhTeuthrienrgPm=acNhTPihn.eeWrse)eaarwereonth’tergoinitnertoesdtientgairlesshueltrse,thbauttinthdeiciantetetrheaste reader is referred to “relativized classes” where programs (or Turing
There are other interesting results that indicate that “standard techniques” won’t ThereNaPre-octhoemr inptelretstein:g2recsualstsethsat indicate that “standard techn
reader is referred to “relativized classes” where programs (or Turing machines) a acle”a(complex)questionan1d9.3t.hHAisRDcPoROsBtsLEjMuSstonCHeAwuPTnoERritk19o.tfHoOtWpimrHoAevR.DeISwAhPReOtBhLeErM?P=NP.Wewon’tgointode allowed to ask an “oracle” a (complex) question and this costs just on
work to prove whether P = NP. We won’t go into details here, but the interested
work to prove whether P = NP. We won’t go into details here, but t allowed to ask an “oracle” a (complex) question and this costs just one unit of tim calledBaker-Gill-SolovayTheorem[1]hasbeengreoaudnedrbisrereafke-rredto“relativizedclasses”whereprogra
In that respect, the so-called Baker-Gill-Solovay Theorem [1] has been reader is referred to “relativized classes” where programs (or Turing machines) are
reader is referred to “relativized classes” where programs (or Turing m
In that respect, the so-called Baker-Gill-Solovay Theorem [1] has been groundbrea ere can be no relativizing proof for P = NP. allowed to ask an “oracle” a (complex) question and th
e no relativizing proof for P = NP. In that respect, the so-called Baker-Gill-Solovay Theorem [1] has been groundbreak-
t What next?
n
ing a
s
allowed to ask an “oracle” a (complex) question and this costs just one unit of time.
Wh
ext?
NP
N
N
b
a
P-
rd
P-h
-co
i
t
ainllgoawseitdshtowaskthant th“eorreacalne”bean(ocoremlaptilveixzi)ngquperosotifofnoraPnd= tNhPis. costs just one
ha
ard
shows that there ca
RR
n
In that respect, the so-called Baker-Gill-Solovay Theore
In that respect, the so-cailnlgedasBitaskheorw-Gs tihlla-tSthoelorevcaaynTbheenorreemlat[iv1i]zihnagspbroeoefnfg
ing as it shows that there can be no relativizing proof for P = NP.
ing as it shows that there can be no relativizing proof for P = NP.
compare problems within complexity classes and define in a
What next?
non-empty by Ladner’s Thm.
NP
P = NP = NP-complete What next?
mp
lete
We have seen how to compare problems within complexity classes a We have seen how to compare problems within complexity classes and define in
P
ones. We have also seen Wsomhearetsnuletsxtth?at provide a recipe how
precise way the hard ones. We have also seen some results that provide
precise way the hard ones. We have also seen some results that provide a recipe ho We have seen how to compare problems within compl
problem in hard w.r.t. a class if we already know another such
to show that a given problem in hard w.r.t. a class if we already know
to show that a given problem in hard w.r.t. a class if we already know another suc precise way the hard ones. We have also seen some resu
uction. We are mainly interested in the class NP, so in the next
hard problem via reduction. We are mainly interested in the class NP,
We have seen how to compare problems within complexity classes and define in a
P6=NP P=NP
We have seen how to compare problems within complexity classes an
hard problem via reduction. We are mainly interested in the class NP, so in the ne
to show that a given problem in hard w.r.t. a class if w lly meet a first NP-complete problem. Then we will also show
chapter we will actually meet a first NP-complete problem. Then we w precise way the hard ones. We have also seen some results that provide a recipe how
rlwld
of Chap. 17 are NP-complete and we will look into games and
pcrheacpitesreweawyilt
“aT
oyp
e-cNP
aolmsoplesteepnrosbolmeme. rTehseunltwsethwaitllparlosovisdheo
Flh
e
Hint: Chap. 17, Exercise 6.
iga.
eswt”
=
1c9th
a .4u:
o
n ibel
omss
wto
dsfivri
e
es
hard problem via reduction. We are mainly interested i
.arl
W
that all the problems of Chap. 17 are NP-complete and we will look in to show that a given problem in hard w.r.t. a class if we already know another such
e
h
oNa n Pv
that all the problems of Chap. 17 are NP-complete and we will look into games an to show that a given procbhalepmteriwnehwairldl awct.ura.tl.lyamcelaetssa fiifrswt NePa-lcroemadpyletkenporowb
and confirm that some famous ones are “hard” in the formal
puzzles as problems and confirm that some famous ones are “hard”
hard problem via reduction. We are mainly interested in the class NP, so in the next
sense explained in this chapter.
14
chapter we willseancsteuaelxlpylamineedt ianfithrisst cNhPap-tceor.mplete problem. Then we will also show
puzzles as problems and confirm that some famous o
1. Recall the problems Max-Cut and Integer Programming from Chap. 17. Show
chapter we will actually meet a first NP-complete problem. Then we w
that Max-Cut P Integer Programming.
that all the problems of Chap. 17 are NP-complete and we will look into games and
sense explained in this chapter.
that all 8the problems of Chap. 17 are NP-complete and we will look in
2. Recasllethee Pprrooblpem.s20.-1 Knapsack and Integer Programming from Chap. 17. puzzlesasproblsemePsroapn.d2.1confirmthatsomefamousonesare“hard”intheformal
8
puzzles as problems and confirm that some famous ones are “hard”
END
© 2008-21. Bernhard Reus, University of Sussex
Next time: Next time:
Example of NP-complete ?
problems
15