Limits of
Computation
18 – The One Million Dollar Question Bernhard Reus
1
A Complexity Class for Problems
from Last Time
• last time we have seen many problems which have not been shown (yet) to be in P but …
• … we can show that their solutions can be checked in polynomial time
• … which leads to a new complexity class.
• BIG QUESTION: does this new class really contain more problems than P?
THIS TIME
www.travellingsalesmanmovie.com
2
Recall from last time
• We have seen several problems that …
• … can be decided easily by “brute-force” search which unfortunately does not have polynomial time complexity so they do not prove that the problems are in P.
• But it can be checked in polynomial time whether a potential solution is actually a solution.
• we will now introduce a new class to capture those problems using this idea.
3
Complexity Class needed
• For those problems in Lecture 17 we need a complexity class.
• We use the idea of a “verifier” that can check in polynomial time whether a candidate solution is a solution of the problem.
• The candidate solution is expressed generally as a “certificate”, an extra argument to the “verifier”.
• This is, of course, weaker than a decision procedure!
4
oretical) Computer Science (Sect. 18.5).
First of all, let us define the new complexity class. We make use of the fact (we
already observed) that the problems for which no polynomial time decision proce-
dure is known, have something in common: namely that one can check whether a 18.1 The Complexity Class NP
given candidate solution is actually a solution in polynomial time. A program that
can perform such a check is a “verifier”. We thus define:
First of all, let us define the new complexity class. We make use of the fact (we Definition18.1(Verifier). AL-verifierforaproblemA✓{0,1}⇤ isaL-program already observed) that the problems for which no polynomial time decision proce-
p (that always terminates) such that
dure is known, have something in common: namely that one can check whether a
New com
plexity classes
given candidate solution is a⇤ctually a solution in polynomial time. A⇤program that A={d2{0,1} | JpK (d,c)=trueforsomec2{0,1} }
L
can perform such a check is a “verifier”. We thus define:
The extra input c is called the certificate used to verify that d is in⇤ A and c may be
Definition18.1(Verifier). AL-verifierforaproblemA✓{0,1} isaL-program different for different instances d. The runtime of a verifier is measured only w.r.t.
p (that always terminates) such that d and not the certificate c.
certificate c for a d A={d2{0,1}⇤ | JpKL(d,c)=trueforsomec2{0,1}⇤}
In analogy with the definition of TIME in Def. 13.2 we can now define a class of problems based on their verifiers:
IMPORTANT: time is considered only in the size of input d, not the certificate
The extra input c is called the certificate used to verify that d is in A and c may be Ddeiffifenrietniotnfo1r8d.2if.fe1r.enTthiensctlanscseosfdp.roTbhlemrusnLti-mveroififabvleriinfiteirmiesmfeisa:suredonlyw.r.t.
d and not thLe certificate c. ⇤ time( f ) NTIME (f)={A✓{0,1} |AhasanL-verifier p2L }
2. NPL is the class of problems that have polynomial time L-verifiers, or in other In analogy with the definition of TIME in Def. 13.2 we can now define a class
words, NPL = {A ✓ {0,1}⇤ | A has an L-verifier p 2Lptime } of problems based on their verifiers:
3. NLINL = {A ✓ {0,1}⇤ | A has an L-verifier p 2Llintime } Definition 18.2. 1. The class of problems L-verifiable in time f is:
4. NEXPL = {A ✓ {0,1}⇤ | A has an L-verifier p 2Lexptime } NTIMEL(f) = {A ✓ {0,1}⇤ | A has an L-verifier p 2Ltime(f) }
As usuaLl, we drop the superscript if the language in question is clear from the context 2. NP is the class of problems that have polynomial time L-verifiers, or in other
or irrelevant. L ⇤ ptime words,NP ={A✓{0,1} |AhasanL-verifier p2L }
Now, wLhy are those cl⇤ass called NTIME, NP, NLlinItNim,e and NEXP, respectively? 3.NLIN ={A✓{0,1} |AhasanL-verifierp2L }
5
The “P” oLf course stands⇤ for “Polynomial” (time) bexuptimwehat about the “N”? The 4.NEXP ={A✓{0,1} |AhasanL-verifierp2L }
3ARsecuaslulathl,atwtheederxopontheentscuapnebrescarpipotlyinfothmeiallaingnu.ageinquestionisclearfromthecontext or irrelevant.
Now, why are those class called NTIME, NP, NLIN, and NEXP, respectively? 234
The “P” of course stands for “Polynomial” (time) but what about the “N”? The 3 Recall that the exponent can be a polynomial in n.
Why the name NP?
• NP stands for nondeterministically polynomial
CHA•PTER 18. P = NP? 18.3. ROBUSTNESS OF NP the reason for this is the following:
Theorem 18.1. A 2 NPTM if, and only if, A is accepted by a nondeterministic Turing machine (NTM) with polynomial time bound. Similarly, A 2 NLINTM if, and only if, A is accepted by a nondeterministic Turing machine (NTM) with linear time bound and A 2 NEXPTM if, and only if, A is accepted by a nondeterministic Turing machine (NTM) with exponential time bound
Proof. Let A 2 NPTM. We have to construct a nondeterministic Turing machine explanation of “accepting” follows
(NTM). This machine simulates the verifier by guessing the certificate nondetermin- istically. It is important here that the certificate has a size polynomial in the size of the input. This ensures that the runtime of the NTM is polynomial according to
234
Def. 18.4 For the reverse direction, assume M is a NTM that accepts A. One con- 6
structs a deterministic verifier that simulates the execution path of the NTM deter- mined by the certificate (which is an additional parameter to the verifier) describing corresponding guesses of M. Since the certificate has a length polynomial in the size of the input, the runtime of the verifier is polynomial.
22
A
r
22 Nondeterministic Nondeterministic Computati
D
w
p
T
tationp⇧s t is acceptin1
s by definiti by nondeter
22
Nondeterministic Comput
A nondeterministic program is one nondeterministic program is one that may “guess,” i.e.
A nondeterministic program is one that may “g relation is multivalued rather than
Nondeterministic Programs
relation is multivalued rather than a partial fun elation is multivalued rather than a partial function, as
•
capacity may be added to any of
capacity may be added to any of the imperat
apacity may be added to any of the imperative comp
for TM add a construct
adding a single instruction form ⇥:
adding a single instruction form ⇥: goto ⇥⇥ o dding a single instruction form ⇥: goto ⇥⇥ or ⇥⇥⇥. Its
transitiroannrseiltaitoionnroeflaFtigiounreo7f.1Ftiogualrseo 7al.l1owtot ransition relation of Figure 7.1 to also allow transitions
• •
the semantics of which is
(⇥, ) ⇤ (⇥⇥, ) and⇥ (⇥, ) ⇤ (⇥⇥⇥, ) (⇥, ) ⇤ (⇥ , ) and (⇥, ) ⇤
(⇥, ) ⇤ (⇥⇥, ) and (⇥, ) ⇤ (⇥⇥⇥, )
so program execution does not produce a
Correspondingly, one makes a while program n transition sequence of states but a tree of states.
Correspondingly, one makes a whil • mand,” for example
forWHILEyoucamnadnodt,h”isfotrooex:admdpalecommand orrespondingly, one makes a while program nondeterm
and,” for example C ::= choose C1 or C2
C ::= choose C1 or C2 with the natural semantics: Either command C
C ::= choose C1 or C2
Note that nondeterministic programs are /e
cutationmo
a t
e program n Cinisticbya
m
t
2ic2a p⇧s ⇤s
with the natural semantics: Either command C 7
the same input may give rise to many di⇥erent computations, Note that nondeterministic programs are /e
with the natural semantics: Either command C1 or command C2 m terminate, and some which may terminate with di⇥erent out
the same input may give rise to many di⇥erent Note that nondeterministic programs are /em not functional in a
terminate, and some which may terminate wit ttions,some
in other words the semantics of computati8on models has not any longer a functional
This is sometimes called “angelic nondeterminism”: Input d is acc
type
of a search through the tree of all possible comp
specify how such a seque
J KL : L-data ! L-data
at least one sequence of “guesses” leading to output true, but th since there is no unique result any longer. Instead the semantics is now a relation
between input and output.
succeeded?in finding a branch ending in “accep
nce can be obtained. One can think of acc
L
L-data L-data
that may “g
one whose uess,” i.e. one
a partial fun
ction, as has b has been th
the imperat ive computati
goto ⇥⇥ o r ⇥⇥⇥. Its sema
semantics i ranlsoitiaolnlsow t
(⇥⇥⇥, ) ondeterministi
1 or command m not function
he same input may give rise to many di⇥erent computa
18.2. NONDETERMINISTIC
PR
i
n of n
22.1 Definition of nondeter
erminate, and some which may terminate with di⇥eren Definition 22.1.1 A computation p ⇧ s1 ⇤ s2
Nondet. Program Runs
e
writes the output true. An input d ⌅ L data is sinit
s000 s001 s01
s 100x
1s
c
D
s0000 s0001 s00
s
s1 000
s
s
s11
s1 1
c nondetermin
T
e
e
i
01
2
o
x
101
s110
s
s
s call
d
“
y
2
OG
h
so
e
set
(p) s101
acc
.
RA
1
D
fi
s100
rites the output true. An input d ⌅ L data is accepted
m
MS
C
eti
his hasatleastoneacceptingcomputationp⇧s ⇤s ⇤.
m
A
c
0
1
HA
1x
at least one sequence of “guesse s” leading to
s0000x s0010 s0011 s10000
he set Acc(p) ⇥ D accepted by p is by definition
1001
x
s10001 s1011y
specify how such a sequence can be obtained.
10
s1101y
of a search through the tree of all possible comp
s0000y s0010x s0011x .s.
s10000x s100010 s100011 s1011z
This is sometimes call
⇥
e
11x
00
01 s1101x
12
n
a
i
t
2.1
p has at least one accepting computation p ⇧ s
Definition of nondeterminist
The set Acc(p) ⇥ D accepted by p is by definiti s0x s10 s11
PTE
s0 s1
Definition 22.1.1 A computation
R 18
.
P=
N
nge
Acc(p)={d⌅ |paccepts
ed “angelic at least one sequence of “guesses”
. 0010y s00110 s00111
succeeded in finding a branch ending in “accep
. Acc(p). = {d⌅ |p accepts d} .
Fig. 18.1: Configurations of a sample run of a nondeterministic program
specify how such a sequence can b
l
i
P?
1
writes the output true. An input d
s1
p has at least one accepting compu
s00 s01
efinition 22.1.1 Acomputationp⇧s ⇤s ⇤…⇤s
1x Acc(p)={d⌅ |pa1ccepts2d}
T
pted by p i 111
s10
s
0
101
ministic
t outputs. ⇤…⇤s isa
ondeter
accepted by no ⇤s ⇤…⇤
1
cce
on ⌅L data is
ism”: Inputd ..⇤st with
output true, d}
One can think
tations on the
nondetermin t.”
leading to 335 e obtained.
t
2
JK✓⇥
?
e
C o
u
n w
h
a
c
c
e e
i o d
r
n
s r
o d
a
1
m
a p
m
n
s
p
a
⇤
g
⇤
o m
b
g i
o
O
e t
e t
i
18.2. NONDETERMINISTIC PROGRAMS
CHAPTER 18. P = NP?
8
p
h
n o
e
i i
r h
ue cs e
e h
c
e o
i h
T w
We already know that p runs in polynomial time so it is also a polynomial verifier.
minimal accepting sequence with respect to runtime. nimal accepting sequence with respect to runtime.
Fig. 18.1: Configurations of a sample run of a nondeterministic program
18
otherwordstonal .2.1 Time
Th
bo
enextprobslentime
cethereisunsation undsfornonution
tween input a quence.Analntime
sinit ss
01 .2.1 Time Measure of Nondeterministic Programs
he semantics of computation models has not any longer a functi Measure of Nondeterministic Programs
s0x s10 s11
e next problem that occurs is that we need to change the definition of runtime
No
n
det. P
s0000 s0001 s001x L s01y s1000
s1001x s1011x s1100 s1101
hichs00m00exasusriems00
a 00ls
f
it1
rogr
unds for nondeterministic programs since we now have more than one execution
11x eqmuentche.aAtnoaclocguoruslyistoththaetiwnpeut/noeutepduttboehcahviaonurgoenethgendereafilisneistitohenruonftirmue
0
0
01
10
oageumnieqausuererteimsuelftroamnayfuloncntgioenrt.oIanrsetleataiodn.the semantics is now a rel deterministic programs since we now have more than one exec
J K ✓L-data⇥L-data
aerltyim, st
m
1f1oer emacesh1
time ndL ✓ L-data ⇥ N
p
. Let p be a nondeterministic L-program. The time usage relatio
•
tcomes foar arneylacthioince: instruction) according to the old Def. 12.1 and Def. 12.4,
lh0
efore have to redefine the class of problems decidable by nond
0ei 0
0i0nueraerse1
s0000y s0010x s0011x s10000x s100010 s100011 s1011z time ndL ✓ L-data ⇥ N
s1101y
p? fined for the above relation as follows:
ox00er
0
10
mr asfiisxendonwsu11m01xber of 1oy
mspesctwiveitlyh.iTnhaengaivtiemne mtimeaseurbeofuncdti.onInfosrtenaodndoetfer“mdineicstidcepdrogbryam”swcaenubse
by” (pointing thus out that a nondeterministic program is used) s the. time for each linear execution sequence (for a fixed. numb
. L s0010y s00110
. timep(d)=min{t|(d,t)2timendpsuchthatpacceptsinputd}.
s00111 L . n(yAchcoeipcteedinsetrtuocftiaon)oancdceotredrimngintoistihceporlodgDraemf.)1.2A.1naondeDterfm.
e runtime of a nondeterministic program p is therefore the shortest length of an eanccaeptitmseinpmuetadsuirfe(dfu,ntrcuteio)n2fJoprKno.nTdhetesremtAincics(tipc)p✓roLg-rdaamtas,c
Fig. 18.1: Configurations of a sample run of a nondeterministic program
cepting path in the tree of configurations, i.e. the minimal possible time it takes to above relation as follows:
ccepted by p, is defined as follows:
cept the input. In Fig. 18.2 some (assumed) accepting paths in the configuration
a
J KL : L-data ! L-data sss?ss
0
101
•s s s s s s s s s
nd output.
semantics is not longer a function but a relation,
000 001 01x
100x 1001
1010 1011 110 111
ogously to the input/output behaviour one generalises the ru efinition 18.4. Let p be a nondeterministic L-program. The time usage relation for
relating input values and possible outputs:
tisimofetyfpreom a function to a relation.
m Se
L
??
1cnutoiondsetq.upernocesg
mantics
r(1fa
e
D
age measurep finition18.4nfor
w
Wewillthereter- s of type ou
nisticprogrraeethe
de m“accepted.
ichmeasureerof
tficnomitieosnf1o8r.a3 1in2i.s4-, Th
pLe-cptriovgerlya.mTphanllebde ac
fined for the set of data a
ac
tree finroomtheFriwg.or1d8s.t1hehsaevmeabnetiecns ohfigcohmligpuhtaetdio.nTmhoedsehlsohrtaessntoatcacneypltoingepratfhuncistiothnaelone
5 timeL(d) = min{t | (d,t) 2 time ndL such that p accepts input d }
Acc( p) = { d 2 L-data | 9p accepts d } pmovitnypgeright through state s1 and endingpin (accepting) state sacc2.
J KL : L-data ! L-data Usingtheabovedefinitiongivesoneanotherway?todefinetheclassNPL,namely
e runtime oafs tahencolansdseotfeprrmobilnemisstiaccpeprotegdrbayma nponidsetehrmerienifsotirceLt-hpreogsrhamorwteitshtaleponlgyntho-of an since there is no unique result any longer. Instead the semantics is now a relation
mialbteimtweeebnouinnpdut(ancdcorudtpinugt. to the above).
cepting path in the tree of configurations, i.e. the minimal possible time it takes to
The Reader might wonder what happens if there are no accepting sequences t. In Fig. 18.2 some (assumed) accepting paths in the configur
J KL✓L-data⇥L-data
hatsoever for nondeterministic program p with input d. Then the above definition
?5 can’t use “decided by procedure” due to non-determinism
8.1 have been highlighted. The shortest accepting path is th
We will therefore have to redefine the class of problems decidable by nondeter- 236
Nondeterministic Programs
rough state s and ending in (accepting) state s .
ministic program1s within a given time bound. Instead of “decideadccb2y” we use the
he kind of nondeterminism that corresponds to requiring that all computation sequences need
term “accepted by” (pointing thus out that a nondeterministic program is used). L ove definition gives one another way to define the class NP , na be accepting is called “demonic” instead.
irthoDlbefinlgentimhti7osna18c.c3e(ApctceedptebdyseatonfaonodnedteeterrminisitsictipcroLgr-apmr)o.gArnaomndewterimthinisa-po tic L-program p accepts input d if (d,true) 2 JpKL. The set Acc(p) ✓L-data, called
d (according to the above).
the set of data accepted by p, is defined as follows:
might wonder what happen2s37if there are no accepting sequ
Acc( p) = { d 2 L-data | p accepts d }
nondeterministic program p with input d. Then the above defin
18.2. NONDETERMINISTIC PROGRAMS
CHAPTER 18. P = NP?
s0000x s0010
s0000y s0010x
s0011
s1101 s1101x s1101y .
sinit
s0 s0x
s1
s00 s01 s100 s101 s11x
s000
called “demonic” instead.
236
s0 1x
s10000 s10001 s1011y s10000x s100010 s100011 sacc2
Fig. 18.2: Configurations tree with accepting paths in red
yields time ndLp(d) = min 0/ which usually is defined as +•. Since our time func-
Example: accepting paths
s001 s0000 s0001 s001x
s1 00x
s100
s101
s10
s110
s111
s0011x
. s0010y sacc1 s00111
237
s10
s11
determinism that corresponds to requiring that all computation sequences
1
s01y s1000 s1001x s1011x s1100
0
11
cepttheinpuation w
efromFig.1eone
ving right th 4T
Usingtheabmely to
5 theclassofwplyno-
al time boun TheReaderences atsoeverforition
he kind of non be accepting is
ith length 7
need
tions have to have results in N? we instead define time ndLp(d) = ? if p does not have any accepting sequences for input d. If time ndLp(d) = ? then all sequences are either non-terminating or produce a result that is different from true.
18.2.2 Some Basic Facts about NP
The first observation is that P is contained in NP:
Proposition 18.1. P ✓ NP.
Proof. Let A 2 P. Just use the program p that decides A in polynomial time as verifier. It does not need an extra certificate, so the certificate is the empty string.
10
Robustness of NonDet. Computation
• we can show that with nondeterministic programs we cannot solve more problems…
• … as they can be simulated by deterministic
ones using exponential slow-down.
Proof: write an interpreter that does dove-tailing for each alternative at a choice command.
•
Evidence for Church-Turing Thesis
11
Results about NP
12
e either non-termnoindaetienrmgionirstpicroprdougcraemainrteosaudltetehrmatiniisstdicifofneer.eTnhtisfrcoanmbetrduoen.e by the concept 8
h
r
r e
l
be many nondeterministic commands in a program, the tree of possi
Basic Facts about NP
steps can branch quite enormously, in the worst case after n steps t
2n different execution branches. This means that the runtime of this in
Results NP
applying the interpreter to the program in question we get a new progra
be exponentially slow (in the number of nondeterministic jumps taken) ation is that P is contained in NP:
deterministic.Notethattheexponow-downinthesimulating
.1. P ✓ NP. Why? programisactuallythe“intendedon”forusingnondetermini
in the first place. P.JTuhsetaunsweetrhteotpherosgecroanmdqpuesthtioantidseaclsiodenso.Anianlogpooulsylyntomthiea
Robustness
case (P) we get the following:
not need an extra certificate, so the certificate is the emp
w that p runs in polynomial time so it is also a polynomial Theorem 18.2. Aside from data-encoding issues
NPTM = NPSRAM = NPGOTO = NPWHILE
d at the beginning of this chapter, the reason for the “N” in
rem:
The proof is similar to the P version in the deterministic case, the only
that for NP we have to compile the verifier rather than the decision pr It is worth pointing out that all problems in NP are also automatica
ential sl motivati
.2.2 Some
e first observ
oposition 18
called “dove-tailing”6. We run all the different possible computation sequences in a sequential way. One can e.g. write an interpreter for nondeterministic programs that simulates the execution of all possible branches concurrently. Since there can
ble transition here could be terpreter will . By partially m that is now deterministic stic programs
oof.LetA2ldettiemrmeinaistic ifier.Itdoestystring.
already kno
As mentione lowing Theo
verifier.
NP is the
difference is ocedure.
lly in EXP.
Proposition 18.2.
23813 TM TM NP ✓EXP
Proof. Assume we have a problem A 2 NP. We know by Thm. 18.1 that A is ac- cepted by a NTM in polynomial time in the sense of Def. 18.4. Assume this polyno- or A that runs lly all the po- order to avoid d path returns as to wait un- ns false. Each p1(|x|). Since on procedure
t if a set and its ail” is split and a lock step way
mial is p1. We have to produce a deterministic decision procedure f
in exponential time. We do this “brute-force” by simulating sequentia
tential paths the NTM may take with input x in a breadth-first style in
Problems in NP
true the deterministic program returns true as well. Otherwise, one h
getting caught in a non-terminating path. Whenever one such simulate
til all paths (they are all of finite length) have executed fully and retur
Theorem: TSP, Graph-Colouring, 0-1Knapsack, and choice doubles the number of paths the length of which is bounded by
Integer Linear Programming are in NP.
each step of a Turing machine costs one unit, the deterministic decisi
1
•is O⇣2p (n)⌘. This proves that A is in EXP.
•
Check that the verifier runs in polynomial time in the size of
Write a verifier that takes as input the instance (graph etc),
and quality measure K, and as certificate a candidate solution (a 6 tour, colouring, packing, variable assignment etc).
• We have used “dove-tailing” in Chap. 9, Exercise exercise:doveTail to show tha complement are both semi-decidable then the set is already decidable. The “dove t
It must verify that the candidate solution is actually a solution
the computation we do needs to be split up into all those potential computations (in
for the given instance (scenario) of quality K or better. in order to avoid running into a non-terminating computation).
the input scenario.
240
14
Check e.g. for TSP
• The certificate here is a list of cities (path/tour).
• The verifier needs to add up the distance of the edges between the cities of the path in given
order and compare them with K.
must also check that • all nodes are visited
This can be done in time O(|V|), so polynomially in the size of the graph.
15
P = NP ?
are NP problems
“feasible” after all?
The most famous BIG OPEN PROBLEM in Theoretical Computer Science
16
• •
P = NP ? Evidence so far suggests that this is not the case.
Here is what Scott Aaronson (MIT) says:
“If NP problems were feasible, then mathematical creativity could be automated. The ability to check a proof would entail the ability to find one. Every Apple II, every Commodore, would have the reasoning power of Archimedes or Gauss.”
17
11 August 2010
Recent proof attempt of P=NP failed!
18
END
© 2008-21. Bernhard Reus, University of Sussex
Next time:
which problems in NP are actually really “hard”?
19