CS计算机代考程序代写 compiler Java capacity planning algorithm Limits of Computation

Limits of Computation
17 – Common Problems Not Known to Be in P Bernhard Reus
1
Last time
• how optimisation problems can be expressed as decision problems
• a number of famous, natural,“real-life” problems that are all provably in P
2

Complexity of natural problems
THIS TIME
• •
e.g. finding the best route
http://xkcd.com
We introduce some more natural (and famous) problems and discuss their runtime complexity.
For those problems today we don’t know whether they are in P and the question remains: “are they feasible?”
3
Problems that look intractable
• •
• •
we introduce more problems, all highly relevant in practice.
which can be solved easily by “brute-force” search algorithms but unfortunately these algorithms do not have polynomial runtime so they do not prove that the problems are in P.
But it can be checked in P whether a potential solution is actually a solution (more about this next time).
Now all problems (even optimisation problems) presented as decision problems for simplicity.
4

Problems of which we don’t know whether they are in P
and that we conjecture may be “intractable”
5
§II.3 An Introductory Real-Life Example The Traveling Salesman Problem (TSP)
Travelling Salesman Problem
• A traveling sales representa- ee Lecture 1, now presented as decision problem
247 145
196
Bristol
260
Birmingham
160 196
s•
a road map of cities, with
tive has to visit n regional
Instance:  
distances attached to road
Cambridge
o⇥ces (clients) in di erent cities.
B
•
Brighton
• The representative wants to segments, two cuitseiehsis nAewacnomdpBanyacnard, soa
93
189 London
91
39
number K Question:  
a map of the cities with dis- tance in km is provided.
109
Eastbourne
• Your task: schedule the vis- its minimizing the total dis- Is it possible to tankcetravetrseipd. from A
278
A
to B which passes through all cities and with a total trip length less or equal K (km) ?
distances in km
in Lec.1 we had A=B
in practice: for distribution of goods
6
16

Press coverage about TSP
24.10.2010
7
How many colours?
•
• •
• 4 is always enough for maps; 
proved by K.Appel & W.Haken in 1977 [“Every planar map is 4-colourable” Illinois J. Math. 21], already observed by Englishman Francis
Guthrie in 1852
(fully machine-checked proof in 2004)
How many colours do you need to paint a map such that no adjacent count(r)ies have the same colour?
on the right 4 colours are used
are 3 colours enough?
http://www.doc.ic.ac.uk/~vf05/atp/casestudy.html
maps are special graphs (planar graphs) where nodes are countries and edges between countries exist if the two countries have a common piece of borderline.
8

•
•
Instance:  
a graph and a number K of colours to be used where K is greater or equal 3 (otherwise it’s easy).
for maps the only interesting (hard) case is k=3
Graph Colouring Problem
CHAPTER 17. HARD PROBLEMS 17.3. MAX-CUT PRO
Question:  
Can one colour the graph in a way that each pair of adjacent nodes (connected by an edge) uses two different colours (using only the K colours provided)? 
Fig. 17.1: A coloured (non-planar) graph
in practice: needed for register allocation in compilers, for traffic
17.3 Max-Cut Problem
channel assignment (networks and InaSeicrt.)1;6.c5.o4 wnefhlaivceteinncoguntreresgthiesMteaxr-Fsl/owplaandnMeisn-/Cjuot pbrosb/lem.
consider now a variation of the flow-cut problem, where we look for max
frequencies have a common edge,
capacity in the cut between the edges of two subsets of vertices in the ne (grcapohl).oTuhisrpsro=blemhisocwalledmMaxn-Cyut.rAessaoduecriscioen spronbleme, dMeaxd-Cut
described as follows:
at any time?
Definition 17.3 (Max-Cut problem).
• instance: weighted graph G = (V,E,w) where w(u,v) 2 Z describes the mum capacity of flow from u to v, and a number K.
• question: can we partition, i.e. cut, the vertices V into two sets S and T suc
9
Let us imum twork can be
maxi-
h that the weight of all edges E between a node in S and a node in T is greater or equal
than K?
In a simplified version there is no weighting and one is interested in the partition with the most edges between S and T. The Max-Cut problem has important ap- plications in VLSI16 circuit design. The partitioning of the circuit into subsystems is essential for optimizing connectivity of components and this partitioning can be optimised with the help of Max-Cut.
Given how similar the Max-Cut problem is to Min-Cut / Max-Flow, it is sur- prising that only the latter are known to be in P. Max-Cut is not known to be in P.
BLEM
0-1 Knapsack Problem
•
Instance:  
a set of n items with sizes {w1,…,wn} and profits {p1,…,pn}, the size of a knapsack W, and a threshold K. All values are positive natural numbers.
16 Very Large Scale Integration
227
•
can be packed such that their profits
are at least K without exceeding the in practice: truck
Question:  
Is there a way a subset of the n items javaingrab.blogspot.co.uk/2014/07/implementation-of-01-knapsack-problem.html
capacity W?
loading, capacity planning
10

Definition 17.4 (0-1 Knapsack Problem). i
a
h
v
s
e
o c
o
T
r
T
e f
⇥
i
a
h
v t

V
s
e d
o
c d
d
o r
⇥
We again apply the concept of dynamic programming produce a n ⇥ pmax ⇥ max
on 17.4 (0-1 KnapsacokntPairnoerb(lkenmap)s.ack), W , a vector of n positive integers, representing the profits (or values) of the items, p (1  i  n), and a natural number K
• instance: a vector of n positive integers, representing the sizes, w (1  i  n) i
(or values) of alues) of the item
• question: Is th tion: Is there a w
tainer (knapsa r (knapsack) suc
the total capa otal capacity W?
vector x (1  rxi (1iin),
the container ontainer (1) or no
Ân w i=1
Again, this finds this finds many a
of capacity plan city planning. Th
1u7se.4s.mToHreEth0a-n1 oK re than one cont
HE 0-1 KNAPSA
There are actu e are actually qu
In [8] the proble h1e7p.4robTlehme i0s-p1r he 0-1 Knap
quiring that Ân thatÂn w⇥ix=1
i
nce: a vector of n positive integers, representing the sizes, w (1  i  n)
• question: Is there a way a subset of the n items cani be packed (stored) in the con-
of the items, a natural number, representing the capacity or total weight of the eitems,anaturalnumtaibner,(krenapprseascekn)tsiuncghthaettchaepirapcriotfiytoadrdtsoutapltowaetilgehasttoKf,twhiethoutexceeding
container (knapsacthke),toWta,l caapvaecityorWo?fTnhipsocsaintibveeixnptregsseerds,bryetpwroesineenqtuinalgititehseanpdroafibtosolean ainer (knapsack), W , a vector of n positive integers, representing the profits
vector x (1  i  n), i.e. each x is either 0 or 1, indicating whether item i is in the items, pi (1  i  n), and a inatural number K
i
s, p (1in),andanaturalnumberK
i
the container (1) or not (0):
ere a way a subset of the n items can be packed (stored) in the con-
ay a subset of the n items can be packed (stored) in the con-
nn
ck) such that their profit adds up to at least K, without exceeding
h that their profit adds up to at least K, without exceeding Âwi⇥xi W Âpi⇥xi K
i=1 i=1
0-1 Knapsack Problem (cont’d)
city W ? This can be expressed by two inequalities and a boolean This can be expressed by two inequalities and a boolean
i  n), i.e. each x is either 0 or 1, indicating whether item i is in i.e.eachxiiseitheir0or1,indicatingwhetheritemiisin
Again, this finds many applications in practice: consider truck loading, or any form
(1) or not (0): t (0):
i
i p⇥xK
In [8] the problem is presented in an even simpler version without values and re-
oCfacanpabceityalpsloanrneinpgr.eTsheenstoe-dcavllieadiBnienq-puaclkitiniegsP:roblemislikeKnapsackbutit uses more than one container.
nnn
iw⇥xW Âi
⇥ÂxiW i p⇥xÂiK i 17
There are actually quite a number of similar problems known in the literature .
i=1
quiring that Âi=1 wi ⇥ xi = W . Also for this version no polynomial time algorithm is
i=1 n i=1
known.
mwanhyearepptlhiceaxtiopnrseisncrpibraectihce:scooluntsiiodneratnrducmkulosatding, or any form
pplications in piractice: consider truck loading, or any form
The Knapsack Problem has a special status among the problems mentioned in
ning. Thebseo-acllal0leodrB1in(h-peanckeintghePnroabmlem) is like Knapsack but it e so-called Bin-packing Problem is like Knapsack but it
this section. One might think that there is actually a polynomial time algorithm that
nNeAcoPnStAaiCnKer.PROBLEM CHAPTER 17. HARD PROBLEMS ainer.
CsKolvPesRiOt sBinLceEoMne can pCroHveAtPheTfEolRlow1i7n.g rHesAulRt:D PROBLEMS 17 ally quite a number of similar problems known in the literature .
ite a number of similar problems known in the literature17.
Proposition 17.1. Any instance of the 0-1 Knapsack Problem can be solved in m is presented in an even simpler version without values and re-
eKsentaepdsiancakn Pevreonbsliemmpler version without values and re- sack 2Problem
O n ⇥ pmax , where (as in Def. 17.4) n is the number of items and pmax is the
w ⇥ x = W . Also for this version no polynomial time algorithm is =Wi .Ailsoforthisversionnopolynomialtimealgorithmis
largest profit value.
blem of packing a knap container with items such that a packingaknapsackorerwithitemssuchthata
then?
max ProblemhasaspecialonWgtheypisroKblenmapssmaecnktionnoedtinP
Proof. We again apply the dynamic programming produce a n ⇥ p
m has a special status a problems mentioned in
of the container is not e optimising at the same time the onmtaitnriexrVisofniontegeexrcsewehderdeontgesamtitnhimeusmamweigtihmtoeftahselectionamong
might think that there is actually a polynomial time algorithm that hink that there is actually a polynomial time algorithm that
edthietefimrst.iAitsemasdwecitihsiaotnotpalropcroefidtutrheatwiseartelpealastcev.tThheisopmtaitmrixumcanpabcekcionmgputed s. As a decision procedure we replace the optimum packing
e can prove the following result: rove the following result:
sack or a a contain
concept of status am mong the
xceeded,
,Vo
t
(
)
d
i, p
v
iesni
i
m
by initialising V(0,0) := 0 and V(0,v) = • for all 0  v and then computing in he value of the packed items is above a certain threshold.
of the packed items is above a certain threshold.
i=1 known.
ii
Consider the pro r the problem of
The Knapsack Knapsack Proble
certain capacity
capacity of the c
this section. One tion. One might t
value of the pack
the packed item
solves it since on t since one can p
with one where t
e where the value a nested loop: V(i,v) := min{V(i1,v),wi +V(i1,v pi)} for all 1  n and
Proposition 17.1. Any instance of the 0-1 Knapsack Problem can be solved in ition 17.1. Any ins0tancveof pth.eTh0e-1secKondatpesrmacikn tPherombalxeimumcains obnely sdoefilvned ifinp  v. In cases
Âii i Definition 17.4 (0-1 Knapsack Problem).
on 127.4 (0-1 Knapsack Problem).
O n ⇥ p , where (as in Def. 17.4) n is the number of items and p is the
pmax , whmeaxre (as in Def. 17.4) n is the number of items and pmax is thmeax
17 Bounded Knapsack Problem, Multiple-Choice Knapsack Problem, Multiple Knapsack Problem, •larginestapnrcoefi:t avavleucet.or of n positive integers, representing the sizes, w (1  i  n)
pnrcoefi:t avavleucet.or of n positive integers, representing the sizes, wi (1  i i n)
Subset-Sum Problem, Change-Making Problem and so on. In fact, the are even entire books [11, 9]
of the items, a natural number, representing the capacity or total weight of the e items, a natural ndeudmicabtedrt,ortheopsreepsroebnletminsgalotnhee! capacity or total weight of the
Proof. We again apply the concept of dynamic programming produce a n ⇥ p We again apply the concept of dynamic programming produce a n ⇥ p max container (knapsack), W , a vector of n positive integers, representingmtahxe profits
ainer (knapsack), W , a vector of n positive integers, representing the profits
11
gers where V(i,v) denotes minimum weight of a selection among ere V(i,v) denotes minimum weight of a selection among
the items, p (1  i  n), and a natural number K s, p (1in),andanaturalnumberK
ii 228
with a total profit that is at least v. This matrix can be computed otal profit that is at least v. This matrix can be computed
ere a way a subset of the n items can be packed (stored) in the con- ay a subset of the n items can be packed (stored) in the con-
(0,0) := 0 and V(0,v) = • for all 0  v and then computing in 0 and V(0,v) = • for all 0  v and then computing in
ck) such that their profit adds up to at least K, without exceeding h that their profit adds up to at least K, without exceeding
0-1 Knapsack Problem (cont’d)
(i,v) := min{V(i1,v),w +V(i1,v p )} for all 1  n and min{V(i1,v),w+V(ii1,vp)}foraill1nand
cityW?Thiscanbei expressedbytwioinequalitiesandaboolean This can be expressed by two inequalities and a boolean
e second term in the maximum is only defined if p  v. In cases d term in the maximum is only defined if p  v. Ini cases
i  n), i.e. each x is either 0 or 1, indicatinig whether item i is in i.e.eachxiiseitheir0or1,indicatingwhetheritemiisin
(1) or not (0): t (0):
Can be also represented via inequalities:
ck Problem, Multiple-Choice Knapsack Problem, Multiple Knapsack Problem, m, Multiple-Choice Knapsack Problem, Multiple Knapsack Problem,
nn
, Change-Making Problem and nso on. In fact, the are even entire books [11, 9]
e-Making Problem and so on. In fact, the are even entire books [11, 9]
i iw⇥xW Âi i p⇥xK ro⇥bleÂxmsaliWone!i p ⇥xÂiK i
alone!
i=1 i=1 i=1
where the xi prescribe the solution and must
many applications in practice: consider truck loading, or any form pplications in practice: 2c2o8nsider truck loading, or any form
228
be all 0 or 1 (hence the name)
ning. The so-called Bin-packing Problem is like Knapsack but it e so-called Bin-packing Problem is like Knapsack but it
ne container. ainer.
0-1 Knapsack is thus an instance of Linear Programming ally quite a number of similar problems known in the literature17.
ite a number of similar problems known in the literature17.
which we know is in P. 
m is presented in an even simpler version without values and re-
esented in an even simpler version without values and re-
w ⇥ x = W . Also for this version no polynomial time algorithm is =Wi .Ailsoforthisversionnopolynomialtimealgorithmis
But all solutions must be integers, so we conclude that it is also unknown whether Integer Linear Programming is in P 
Problem has a special status among the problems mentioned in m has a special status among the problems mentioned in
might think that there is actually a polynomial time algorithm that hink that there is actually a polynomial time algorithm that
e can prove the following result: rove the following result:
matrix V of inte of integers wh (or values) of
alues) of the item
the first i items i items with a t
• question: Is th tion: Is there a w
by initialising V alising V(0,0) :=
tainer (knapsa r (knapsack) suc
a nested loop: V loop: V(i,v) :=
the total capa otal capacity W?
0vÂ p.Th Âvpeic.tTorhexi s(ei1con
ii i
rx (1in),
the container ontainer (1) or no
17 Bounded Knapsa ed Knapsack Proble
Subset-Sum Probnlem um Problem, Chang
dedicated to those pw to those problems
i=1 Again, this finds
this finds many a
of capacity plan city planning. Th
uses more than o re than one cont
There are actu e are actually qu
In [8] the proble he problem is pr
quiring that Ân thatÂn w⇥ix=1
i=1 known.
ii
The Knapsack Knapsack Proble
this section. One tion. One might t
solves it since on t since one can p
Â
Proposition 17.1. Any instance of the 0-1 Knapsack Problem can be solved in ition 17.1. Any instance of the 0-1 Knapsack Problem can be solved in
largest profit value. profit value.
On2 ⇥ p , where (as in Def. 17.4) n is the number of items and p is the pmax , whmeaxre (as in Def. 17.4) n is the number of items and pmax is thmeax
Proof. We again apply the concept of dynamic programming produce a n p
12

Complexity of problems? • We don’t know whether the problems on previous
slides are in P.
• Simple “generate and test’’ algorithms are
n = size of graph (number of nodes i.e. cities)
exponential. For instance check all TSP paths: there
§II.3 TSP: Do you have e are about (n-1)!/2 so time bound even worse than
exponential 2N.
•
• We define a new class for which we know that it 14
• if 10 = 10,000 billion tou contains all the problems just presented: (s uper-super-computer) stil
NEXT TIME!
1044 =1030 >>3· 1014
Stirling’s formula:
n! ⌅ ⇤2⇤n(n)n e
13
rs could be checked per l needed:
1018 ⌅ 1011 · 31, 536, ⇤ ⌅⇥
1 yea
⇤ ⌅⇥
estimated age of t
OOOPS! Combinatorial explosion!
• Exponential time complexity leads to intractable ex
nough time?
cities 10 40
tours to che
9! =181,44 2
39! >1044 2
Problems not • TSP known to be
• Graph Colouring
• 0-1 Knapsack Problem
• Linear Integer Programming
in P
and many, many more we’ll meet some more later
14
r
h
e

END
© 2008-21. Bernhard Reus, University of Sussex
Next time: Programs than can “guess” and a One Million Dollar Question!
15

Related Posts