Limits of Computation
16 – Problems in P Bernhard Reus
1
The complexity story so far
• sequential ones P is robust under compilation between any machines/languages (LIN only between
some of them)
• Hierarchy theorems: there exist problems that can only be solved if more running time is available.
2
• •
•
we introduce some natural (and famous) problems and discuss their time complexity.
The problems in this session are all provably in P.
THIS TIME
e.g. finding the best route for Travelling Salesman (next session!)
http://xkcd.com
Complexity of natural problems
For others we don’t know and the question remains: “are they feasible?” (see next session)
3
Important sample
Problems
We introduce a couple of nice problems, all highly relevant in practice.
Optimisation problems:
“find the shortest/ largest …”
we present as decision problems:
“is there a … of size K?”
• This is simpler, fits our definition of problem, and does not simplify the complexity.
• •
4
Decision Problem template
Problem P of the form “decide membership in A”
• Instance: some word (data) d
• Question: Is d in A?
Recall that input is always encoded as word over alphabet {0,1}
• to show that P is in TIME(f(n)) one needs to find a decision procedure for A with
• Input: d
• Output:‘yes’ or ‘no’ stating whether d is in A. •Runtimebound: f
5
Optimisation Problem template
• Instance: some “scenario” G (often a graph)
• Question: find a solution s such that m(s) is minimal/ maximal where m is some (fixed) measure of the size of s.
• to show that P is in TIME(f(n)) one needs to find an algorithm with
• Input: G
• Output: s
• Runtime bound: f
Problem P of the form “find optimal s in G”
6
Reduce Decision to Optimisation
• Instance:some “scenario” G (often a graph)
•
• Instance:some “scenario” G (often a graph) and a positive number K
•
Question: find solution s for G such that m(s) is minimal/maximal where m is some (fixed) measure of the size of s.
Question: is there a solution s for G such that m(s) ≦ K? (or m(s) ≧ K, resp.)?
Why is this a reduction? Why is this sufficient for our purposes?
7
Problems in P
“tractable” by Cook-Karp
8
Algorithm
Time Complexity
Best Average
Array
Sorting
you should know this already! 🙂
•
•
k = length of key in binary
Worst
Quicksort
Ω(n log(n))
Θ(n log(n))
O(n^2)
Mergesort
Ω(n log(n))
Θ(n log(n))
O(n log(n))
Timsort
Ω(n)
Θ(n log(n))
O(n log(n))
Heapsort
Ω(n log(n))
Θ(n log(n))
O(n log(n))
Bubble Sort
Ω(n)
Θ(n^2)
O(n^2)
Insertion Sort
Ω(n)
Θ(n^2)
O(n^2)
Selection Sort
Ω(n^2)
Θ(n^2)
O(n^2)
Tree Sort
Ω(n log(n))
Θ(n log(n))
O(n^2)
Shell Sort
Ω(n log(n))
Θ(n(log(n))^2)
O(n(log(n))^2)
Bucket Sort
Ω(n+k)
Θ(n+k)
O(n^2)
Radix Sort
Ω(nk)
Θ(nk)
O(nk)
Counting Sort
Ω(n+k)
Θ(n+k)
O(n+k)
Cubesort
Ω(n)
Θ(n log(n))
O(n log(n))
Instance: a number array A
Question: What is A sorted?
9
•
•
• •
we know that context-free languages (generated by context free grammars) are decidable (there is a parser).
simple minded algorithm needs to test all possible derivations but there are exponentially many.
Dynamic
Programming use solutions to subproblems you already have; in this case produce a parsing table. Runs in O(|s|3)
Membership test for context-free
languages
But what is the time complexity of parsing ?
Instance: a context free language L over alphabet A and a word s over alphabet A
Question: is s in L?
10
Is a number a prime?
• • •
• That there is an algorithm with polynomial time bound (in this sense) has only be shown in 2002 in a famous (award- winning) result by:
“PRIMES is in P”: Agrawal, Kayal, Saxena (AKS)
Instance: a natural number n Question: is n a prime number ?
Using binary representation of numbers to measure (logarithmic) size of input.
11
Graph
(Optimisation) Problems
12
Lemma 16.1 Every undirected (weighted) graph can be represented as a directed
(weighted graph). Proof Exercise2.
16.5.1 Reachability in a Graph
(Graph) Reachability
Definition16.6 (ReachabilityProblem)
in
also called Graph
stance
•
• question: is there a path from s to t in G?
o vertices s, t ∈ V ; 16 Famous Problems in P
•Givenargerda.TphereGar=e(oVth,eEr)pathsbetween(a)and(g)too,forinstancea→b→f→gor
Accessibility Problem
204
:a
=
(di
d
recte
do
r und
irect
ed)
grap
(V
, E)
tw
hG
Is there a path from a to g?
Example16.4 InthegraphdepictedinFig.16.2thereisapathfromnode(a)tonode Fig. 16.2 Undirected graph a
,a
n
(g). The path is a → d → g and the corresponding nodes in the path are coloured G = (V, E) d
a→d→ f →gorevena→b→e→ f →g. with (un)directed edges
f
E, two nodes s and t: b
Graph reachability can be solved by a simple breadth-first (or depth-first) search
along the edges starting from vertex s. By visiting all edges (and remembering those
• Is there a path p from node s to node t in G?
visited edges) one can traverse the entire graph and find all reachable nodes.
16.5.2 Shortest Paths in a Graph
ce
path: a – d – g or a – b – f – g
G = (V, E) together with a function w : E → R such that each edge has a weight
Definition 16.7 (Weighted graph) A weighted graph G = (V , E , w) is a graph
graph traversal starting from s
can be done in linear time, O(|E|)
expressed as a (real) number.
In the following, all graphs are undirected but the problems can also be expressed using directed graphs.
g
Simple breath-first or depth-first
The graph in Fig. 16.3 is we1i3ghted. In this case all the weights are actually natural numbers in N.
Definition16.8 (ShortestPathProblem)
• instance: a weighted graph G = (V , E , w)
• question: What is the distance of the shortest path from v1 to v2 in G for each pair
•
Fig. 16.3 Weighted graph with shortest path from a to g
a3d 2
of vertices v1,v2 ∈ V? By shortest path we mean the path for which the sum of weights of all the edges on the path is lowest.
Example 16.5 The shortest path from node a to node g in the graph depicted in Fig. 16.3 is a → d → g and the sum of weights of its edges, i.e. the required distance, is3+2= 5.
Instance: a weighted graph G=(V,E,w) with weighted edges E, and two vertices s and t
3 246
g
Shortest Path
• Question: What is
(the length of) the
shortest path from s c to t in G?
“Floyd-Warshall-algorithm”
32
1f b
e
“depth first search” F-W algorithm has runtime O(|V|3)
path a – d – g with length 3+2=5 issues with negative weights
14
REVISED PROOF
REVISED PR
Maximal Matchings
206
16
Famous Problems in P
• amatchinginagraphisasetof Fig. 16.5 A bipartite graph
matching of size 2
matching of size 3
edges such that no two edges in the set share a common vertex.
with two different matchings
• Instance: a graph G=(V,E)
• Question: What is the largest
matching in G?
largest complexity. algorithm has runtime O(|V|4) but there are
The shortest path problems have many applications, for instance in internet routing
“Blossom-algorithm” by Edmonds
Dijkstra’s algorithm and the Flo“yde–pWtahrsfhiarlsltaslegaoricth”mEhdamveotnhdess’sam“Belosrsdoermo”f
protocols. The Open Shortest Path First protocol [23] (OSPF), an interior gateway protocol for large enterprise networks, for instance, can deal with link failures of
better ones
nodes by quickly computing a new shortest path for a route.
16.5.3 Maximal Matchings
16.5. 7 BRIDGES PROBLEM CHAPTER 16. FAMOUS PROBLEMS IN P A matching in a graph is a set of edges such that no two edges in the set share a
15
• question: What is the cut with minimum capacity for the given flow network? common vertex. Often the graph isThbeoipreamr1t6it.1e. ,LetthGawtitmh seouarcnes aintdssivnketrbteicaefloswcnaetnworbke. Thdeimvaixdimeudm flow
is equal to the capacity of the minimum cut.
into two disjoint sets of nodes A and B, such that nodes in A (and B, respectively) Applications of this problem basically occur wherever networks occur: In a com-
are not connected and the edges of the graph always connect a vertex from A with puter network, one may wish to route as many packets as possible. In transportation
a vertex from B. If one wishes to match up pairs of competitors from two teams
the number of trains per any given time. Similar applications arise for road or phone
Max-Flow / Min-Cut
one may wish to send as many trains as possible, where tracks have certain limits on
for a tournament, for instance, onenewtworuksl.dFohr amvore aebodugt tehis pbroebtlewmeaendnitspaappirliscatoiofnsvseer[t3i]c. es that represent members of different teaEmxamsp.leS1i6n.6c. Teheegaracph incFoigm. 1p6.e6atisthowrs iasfloswunpetpworskeasda gtroaph. aTvheelabels
on each directed edge denote capacities. The network’s source node is s and its sink only one opponent, no two edges in the matching should share a vertex. Figure 16.5
•
directed graph G=(V,E,w)
node is t, respectively. In Fig. 16.6b the same network is depicted but edges are now labelled with their maximum flow (in red) instead of their capacity. It is obvious
shows two matchings for the same bipartite graph (where the different sets of vertices
from thflisopiwcturentehatwtheomrakximum flow is 3. Omneacxan afllsowsee ithnatrthedminimum are coloured yellow and purple, respectively). The matching of size two on the left
Instance: a weighted
hand size is highlighted in red, and the matching of size three on the right hand side
is highlighted in blue. Indeed, three is the largest size matching for the given graph.
encoding a flow network,
Definition16.9 (MatchingProblem) source node s, sink node
2322 2323
ss
•
3111 • question: What is the largest matching in G?
11 11 t. • instance: a (undirected) graph G = (V, E);
Question: What is the (Footnote 21 continued)
4545
maximum flow (or cut with
2322 award (among many prizes) in 1972 “for fundamental contributions to programming as a high,
minimumintcelalepctauacl icthya)lleinnge;tfhoreloquent insistence and practical demonstration that programs should be composed correctly, not just debugged into corr(ea)cAtnfloewssne;twforrk aisllguramph inating pe(br)cMeapx-tfliownfoor fthepnreotwbolrkemon sthealteft
given network G?
max. total flow of 4
the foundations of program design” [4].
“Ford-Fulkerson—algorithm”
cut edges (2,4),(3,4), and (3,5) or the pair of edges (4,t) and (5,t). In either case the total flow of the edges is 4.
tt
cut is 4. To completely disrupt the flow from node s to t it suffices for instance to cut
the edges (s, 2) and (s, 3), which together have a flow of 3. Alternatively, one could Ford-Fulkerson algorithm
has runtime O(|E| x maxflow)
16.5.5 The Seven Bridges of Ko ̈nigsberg
Legend has it that Frederick the Great of Prussia once had to host a bunch of in- 16
ternational dignitaries whom he wanted to show the beauty of the city, first and 214
REVISED PROOF
Euler could show that there was no such tour possible by proving a general
17
A variation of this problems, where the length of the route is also important, is the so-called (Chinese8) Postman Problem: given a map of a (quarter of a) city where all streets carry as weights the length of the street, find the shortest tour that visits each street exactly once and returns to the starting point. If we represent this problem graphically we get a graph where streets are edges and vertices are street corners. And a solution is to find a tour that visits all edges
result about such circuits in graphs (now called Eulerian circuits in his honour) i.e. circuits that visit each edge exactly once and finish in the same vertex they started from. This will be explained in the exercises.
c Bernhard Reus, Sussex University 2015
Limits of Computation
The 7 Bridges of Königsberg
• •
•
by the river) and the edges represent the bridges . The land m image are marked green and numbered 1–4 such that the resu like this
(1707-1783) for a tour that usingagraphwheretheverticesrepresentthevariouslandmassebsr(siedpgaerast=ededges,
visits each bridge exactly once.
started from. This will be explained in the exercises.
like this
Euler used a graph (inventing
graph theory); he had to report
back that this is impossible (only possible on certain condition discussed in exercises).
city where all streets carry as weights the length of the street, tour that visits each street exactly once and returns to the sta represent this problem graphically we get a graph where stre
In the above image the river is coloured blue and the bridges Euler abstracted away from the concrete layout of the riv
cBernhardReus,SussexUniversity2015 usingagrapLhiwmhietrsetohfeCveortmicpesurteaptreiosentthevariousland
7
1
24
3
Euler could show that there was no such tour possible by
Frederick the Great wanted to show off the 7 bridges to visiting dignitaries
and asked famous (Swiss-born) mathematician Leonhard Euler
In the above image the river is coloured blue and the bridges red.
river“Pregel” resultaboutsuchcircuitasibnsgrtarpahsc(tnowgrcallpedhEuolerfia
ncircu Euler abstracted away from the concrete layout of the river and bridges by
i.e.
cir
cu
i
ts
th
at
visit each edge exactly once and finish in the
b
d
r
i
g
e
s
7 nodes=land
is the so-called (Chinese8) Postman Problem: given a map o
by the river) and the edges represent the bridges .ATvahreiatliaondofmthaispserosbilenmtsh, wehaebreotvhe length of the route
image are marked green and numbered 1–4 such that the resulting graph looks
find a t1our of requested find
in the graph just like for the Bridges problem above.
vertices are street corners. And a solution is to find a tour th
kind a Eulerian circuit in • instance: a graph G = (V, E)
among the 7 bridges the graph
7thus inventing the field of graph theory on the fly
8
due to Chinese scientist and author Kwan Mei-Ko who seemed to term Postman problem
circuit = closed path with no repeating edges
2 4
3
14
red.
er and bridges by
masses (separated asses in the above lting graph looks
proving a general its in his honour) same vertex they
is also important, f a (quarter of a) find the shortest rting point. If we ets are edges and at visits all edges
have introduced the
in the graph just like for the Bridges problem above. • instance: a graph G = (V, E)
7thus inventing the field of graph theory on the fly
14
8due to Chinese scientist and author Kwan Mei-Ko who seemed to have introduced the term Postman problem
The Postman Problem
• deliver the mail in your
neighbourhood where edges are
streets (= undirected graph); start in
A; ×
also “Chinese” postman problem
due to Chinese author Kwan Mei-Ko
• you want to visit all streets and return to A without visiting a street twice.
• Instance: a graph G=(V,E) √
•
(=street) once ?
like 7 bridges problem = find Eulerian circuit
Question: Is there an (Eulerian)
circuit in G that visits every edge
http://web.mit.edu/urban_or_book/www/book/chapter6/6.4.2.html
Fleury’s algorithm runtime O(|E|2) but there are faster ones
Route Inspection Problem: replace “once” by at least “once”
18
Here is a simple example of an application of Linear Programming from [25]: T
mr l
eo
a( Tr cr
wc
m
g
[e u1
oa
k
lo
mo om
M s
r v
• qu•estqioune:stmioanx:imiazxeimciz·excT ·x 2
Example 16.7. Suppose that a farmer has a piece of land, say A km large, to be
HereHisearesimsaplseimexpalmeepxleamofpalenoafpapnlicaaptpiolincaotfioLninoefaLriPneroagrrParmomgrianmgf planted with either wheat or barley or some combination of the two. The farmer has
a limited permissible amount F of fertilizer and I of insecticide, each of which is 2 ExamEpxleam16p.l7e.1S6u.p7p.oSsueppthoasteathfatrmaefrarhmaserahpaisecaepoiefcleanodf,lsaanyd,AsakymA
required in different amounts per unit area for wheat (F ,I ) and barley (F2,I2). Let amtiboinaotfiothneotfwthoe. Ttwh
• •
•
x1 + x2 A total area constraint F1 ⇥ x1 + F2 ⇥ x2 F fertilizer constraint
Solving linear inequalities
Instance: a vector of positive (real)
P1⇥xP1+⇥Px2⇥+xP2 ⇥x opti maximise 1 1 2 2
Question: maximise cT x Simplex Algorithm
given in Def. 16.15: A 1 1 given in Def. 16.15:
11 plantepdlawntiethdewitihtherewitheratwohrebaatrolreybaorlesyomorescoomebcino
P1 be the price of wheat, and P2 the price of barley, each per km2. Th alimiateldimpietermdipsesribmleissaimbloeuanmtFouonftFferotiflifzerrtialinzderIa
with wheat and barley are denoted x1 and x2 (in terms of km2), res requiredquinireddiffinerdeinftfearmenotuanmtsopuenrtsunpietraurenaitfaorrewa fhoera
farmer would like to optimize the income, and needs to decide how
Linear Programming
P bePthebeprtihceporficwehoefatw,haneadt,PantdhePprtihceporficbearolfeyb,a 11 22
barley to plant. This can be expressed as a linear programming probl with whitehatwahnedatbanrldeybarrleydeanreotdeednxoteadnxd xan(dinxt
farmefrarwmoeurldwloikueldtolikoeptiomoizpetimthiezeintchoeminec,oamnde,naened
P1 ⇥ x1 + P2 ⇥ x2 optimize revenue barleybatorlepylatnot.pTlahnits. cTahnisbceaenxbpereesxsepdreasseadliansearlipnre
I ⇥ x + I ⇥ x I insecticide constraint
1122
wherex1+x2 +x A toAtalatort 12
which gives rise to the following instance of the linear Programmi
variables x, row vector b, matrix A given in Def. 16.15:
such that Ax ≦ b and column vector c
0101
F ⇥xF+⇥Fx ⇥+xF ⇥xF fFertilifze 1 11 21 22 2
I ⇥xI+⇥Ix⇥+xI ⇥xI insIectiincsie 1 11 21 22 2
whichwghivcehsgrivsestoristehetofotlhleowfoinllgowininstganicnestaonfcteheofl
c=(P1P2)
The best performing algorithm on average for Linear Programmi
@A@A
b= F A= F1F2
I I1 I2 AA
c=(Pc=P(P)P)b=bF= F 1212
33 II plex algorithm (also known as simplex method), discovered by Ge
1122
0 10 1
@ A@ A
often cited as one of the top 10 algorithms of the 20th century [9]
Simplex algorithm does not have polynomial runtime (!) Karmarkar gave
3.5 2
polynomial algorithm O(n x L x ln L x ln ln L) where n is the number
The bTehstepbersftorpmerifnogrmalignogriatlhgmoriotnhmavoenraagveefroarge
cussion in Sect. 14.33)3. It does not run in polynomial time though
34
33
plex plaelxgoraitlhgmor(itahlsmo(kanlsoowknnaoswsnimapslseixmmpletxhomde)t,
of variables and L is size of input (binary).
Khachiyan was the first to prove that Linear Programming is in oftenocfittend caisteodnaesoofnteheoftotphe1t0opalg1o0riatlhgmorsitohfmtsheo
32
KhachKihyacnhiyawnas twheasfitrhset tfiorsptrotoveprthovateLthinaetaLrinP It has m rows and n columns.
cussiocnusisnionSeicnt. S1e4c.t3.).14It.3d).oeIts dnoetsrunnotinrunpoilnynpo 34 34
33 In geometry, a simplex is a generalization of the notion of a triangle or tetrahedron to arbitrary 19
dimensions: a k-simplex is a k-dimensional polytope which is the convex hull of its k + 1 vertices. 32 32
It has mIt hroaws ms arnodwns caonldumn cnos.lumns.
The simplex algorithm uses a simplex to describe the solution space (“feasible region”) and then
33 33 IngeoImnegtreyo,maestirmy,palesximispalegxeinsearaglieznaetrioalnizoaftitohneonfothioennoftiaontrioafnaglterioanrgteletraohretdetrr
“runs” along the edges to find the best corner.
34 dimendsiomnesn:saiokn-si:mapkl-esximispalekx-disimaekn-dsiomneanlspiolnyatlopoelwythoipcehwishtihcehcisonthvexcohnuvllexofhiutsll Leonid Genrikhovich Khachiyan (May 3, 1952 – April 29, 2005) was a Soviet mathematician
The siTmhpelesximalpgloexritahlmgouristehsmaussiemspalesximtopldeexsctoribdestchreibseoltuhteiosnolsuptaiocne s(“pfaecaesi(b“lfearseigbi of Armenian descent who moved to the US in 1989. For proving the above mentioned result he
“runs”“arulonnsg”tahloenegdgtheesetodgfiensdtothfienbdesthtecobrensetrc.orner.
was awarded the Fulkerson Prize of the American Mathematical Society and the Mathematical
e areas planted onfdiInsoefctiincsiedcet,iceiadceh,
pectively. The tw(hFea,tI ()Fa,nId )banrldeyb
1111 much wheat 2or
2 eralecyh, peaecrhkmper. Tkmhe.a
em as follow2s: e(rimnsteorfmksmof),krmesp),e
dsnteoedsectoiddeehcoidwe mhou oagrrpamromgrianmgmprionbglepmro
moizpetimreivzenrueevenue
ealcaorneastrcaoinsttraint
errticlioznesrtrcaoinsttraint ng Problem as
dceticoidnestrcaoinsttraint itnheearliPneroagrrPamromgrianmg
0011
1111
@@AA
A = A F= F F F 1212
ng is the sim-
I1 I2 I1 I2
orge Dantzig, (see also dis-
LifnoeraLriPnreoagrrPamromgrianmg [19]. Leonid
hdoidsc),ovdeisrceodvbeyredGeboyr P. His algo-
f20ththe 2ce0nthtucryen[t9u]ry(s omlyianlomtimiael tihmoeugtho[ eroargrPamromgrianmgmisinign iPs
2
• Sorting •
amusinagmaucscinogunatcocofuthnitsosftothryisasntodrhyoawndjohuorwnajloisutrsncaalnistmsicsarne in [21]i.nA[2n1y]w. aAyn,yKwhayc,hKiyhaanc’hsiwyaonr’ksswtiomrkulsatiemdumlautecdh mreusecahr KarmaKrkaarmr’sarbkraera’kstbhreoaukgth.rough.
217 217
Problems in P and many, many more
•Parsing
• Prime Number Test • Graph Reachability • Shortest Path
• Maximal Matching • Max Flow-Min Cut • Postman Problem
Linear Programming
34 34
LeonidLeGoenirdikGheonvriickhhoKvhiacchhKiyhaanch(Miyayn 3(M, 1a9y532,–19A5p2ri–l 2
Programming Society. He even made the front page of the New York Times. A
of ArmoefnAiarnmdenesiacnendtewscheontmwohvoedmtovtehdetUoSthienU19S8i9n. 1F9o8r9p.r amusing account of this story and how journalists can misrepresent scientific res
was awarsdeadwathrdeeFdutlhkerFsounlkePrsiozen oPfritzheeoAfmtheriAcamneMricaathneMm in [21]. Anyway, Khachiyan’s work stimulated much research on the area, even
PrograPmromgirnagmSmoicnigetSy.oHcietye.veHnemevaedne mthaedferotnhtepfarognetopfatghee Karmarkar’s breakthrough.
217
20
A9np,r2inl0s20i95g,)h2twf0ua0ls5aa)nwdSoavsiaetS uFoltvosirncpgarnothvbeienafgbootuhvnedamboenvtei
atihceamlaStoicaieltSyoacniedtythaen tually leading to
oNfetwheYNoerwk TYiomreks.TAimnei pmreiserenptrsecsientisficciernetsiufilcts crehsoeanrctheoanretah,e eavrenat,uea
very versatile
& useful
END
© 2008-21. Bernhard Reus, University of Sussex
Next time:
More practically relevant problems for which no polynomial time algorithms are known.
21