Limits of Computation 2020/21
Part V Complexity: Various Problems and NP(Some notes on Lectures 16–18) Bernhard Reus
March 15, 2021
16 Problems in P
In this section we will have a closer look at some “natural” problems that we encounter quite often in practice. All of them are quite famous (some more than others). In order to solve, i.e. decide, these problems, researchers have found (meanwhile famous) algorithms. By investigating their time complexity we get an upper limit for their running time and thus get an idea in which complexity class the corresponding problem is at least. Of course, it is much harder to show that a problem is not in a given complexity class as this would require a proof that there is no algorithm that decides the problem with a given time bound or a time bound of a given kind.
We can therefore show that a certain group of problems is in P by providing decision procedures that have a polynomial time bound. Although we do not really believe the Cook-Karp-Thesis, those problems can be classified “feasible” since the polynomials appearing as their time bounds have a low degree (up to 3 or 4).
For another group of problems, nobody has found polynomial time algo- rithms yet, so we don’t know yet whether they are in P or not. We discuss them in the next chapter.
Before we look at those two groups of problems let us first define the “tem- plate” for decision and optimisation problems, respectively:
16.1 Decision versus Optimisation Problems
A decision problem is of the form “decide membership in A” (here A is a set of data). Problems (of our kind, recall the beginning of the course) are decision problems. A template for such a problem can be described by stating what the problem instance is and what the problem question is:
• (problem) instance: a particular data d (out of a given set or type) • (problem) question: “is d in A”? (or short d ∈ A?)
1
⃝c Bernhard Reus, Sussex University 2018–21 Limits of Computation
Further more if we want to show that the problem is in TIME(f) we need to find an algorithm (procedure) p such that
• Input: p takes as input a data element d (of the set of allowable data = input type);
• Output: p decides d ∈ A returning true or false as output accordingly; output type is therefore BOOL;
• Time bound: p has a runtime bound f.
An optimisation problem is of the form “find an optimal s in G” and a template
can be described as follows:
• (problem) instance : some “scenario” G (often a graph or something of the kind, in any case clearly defined)
• (problem) question: find a solution s in G such that m(s) is minimal/ maximal where m is some (fixed) measure of the size of s that can be computed in polynomial time in the size of s.
Morevoer, if we want to show that the problem is in TIME(f) we need to find an algorithm (procedure) p with
• Input: G (and potentially some other data)
• Output: solution s such that s is a minimal/maximal solution w.r.t. m;
• Time bound: p has a runtime bound f.
We can reformulate any optimisation problem as a decision problem of the following form:
• (problem) instance: a particular encoding of G and a positive natural number K
• (problem) question: is there a solution s in G such that m(s) ≤ K (or m(s) ≥ K for maximisation, respectively)?
Now why is it ok to consider the decision problem version of optimisation problems? Well, the decision problem is not harder than the optimisation prob- lem. If we can solve the optimisation problem with time bound f then we can solve the decision problem version with time bound g(n) = p(f(n)) where p is a polynomial. Why? Because if we have the optimal solution s (constructed in time f (n) and thus with a size bounded by c × f (n)) we can check whether m(s) ≤ K (or ≥, respectively) in polynomial time in the size of s. So if the optimisation problem is in P so is the decision problem. Contrapositively, if the decision problem is not in P, the optimisation problem is not either. We are interested in problems that are not in P as they are surely infeasible. And according to the above, it is sufficient to consider decision problem versions of optimisation problems.
2
⃝c Bernhard Reus, Sussex University 2018–21 Limits of Computation
16.2 Membership test for a Context free language
We know that context-free languages (generated by context free grammars) are decidable. The decision procedure for such language is simply a parser for that language. But what is the time complexity of parsing ?
• instance: a context free grammar G over alphabet Σ and a word s over alphabet Σn (i.e. in Σ∗)
• question: is s in the language generated by G ?
A simple minded parser would just try all the possible derivations for the gram- mar. But due to branching there may be exponentially many such derivations. One has to do something a bit more clever to get a polynomial time algorithm. The clever trick is called Dynamic Programming which simply refers to the fact that one stores intermediate results of (sub)problems and (re-)uses them cleverly to compute the desired result. This avoids unnecessary re-computation of known results which can speed up the process significantly. Probably the most famous algorithm for parsing is the CockeYoungerKasami algorithm1 (also called CYK, or CKY algorithm). It is named after the scientists who independently invented it in the late 1960s: John Cocke, Daniel Younger and Tadao Kasami. This algo- rithm performs “bottom-up” parsing constructing a so-called parsing table that stores which substrings can be generated from which “non-terminals” of the grammar. The most famous parsing algorithm which runs in time O(|s|3 × |G|), i.e. in cubic time in terms of the size of the string tomes the size of the gram- mar2. Note that considering asymptotic worst case complexity this is the best algorithm for parsing.
16.3 Primality Test
This problem is a true decision problem and thus presented as such.
Definition
• instance: a positive natural number n (the size of the number is measured
logarithmically, i.e. as the number of digits of its binary representation)3;
• question: is n a prime number?
That there is an algorithm with polynomial time bound (in the given strong sense regarding logarithmic size) has only be shown in 2002 in a famous award-
1According to Hopcraft, Ullmann and Motwani’s textbook (Chapter 7), only D.H. Younger’s version was ever published “conventionally” in D.H. Younger: “Recognition and parsing of context-free languages in time n3,” Information and Control 10:2 (1967), pp. 189– 208.
2If the grammar is fixed one usually ignores the grammar coefficient.
3e.g. |102| = |1100110| = 7 whereas in the WHILE cost measure |102| = 103 (a list with 102 nil entries).
3
⃝c Bernhard Reus, Sussex University 2018–21 Limits of Computation
winning4 result by: Manindra Agrawal, Neeraj Kayal, Nitin Saxena5 called “PRIMES is in P”.
The AKS algorithm6 runs in Olog12 n × p(log (log n)) where n is the 222
problem instance (natural number). If we replace log2 n by n as the input of the problem is the binary representation of the number, we obtain On12 × p(log2 n) which is clearly polynomial. Note that the exponent 12, under certain assump- tions, can be greatly reduced.
The “simple-minded” primality test (also called “trial division” that you might have learned already at school – namely to divide the given number K
by all odd numbers up to the square root of K – has a complexity of O√K. If we consider the input number K represented as a binary of n digits then trial
division is O√2n = O2n2 . This is clearly not polynomial.
16.4 Graph Problems
16.4.1 Finding the shortest path in a graph
Recall that a graph consist of two sets: a set of vertices V and a set of edges E. Edges are simply pairs of vertices (s,t) the source and the target vertex of an edge. In undirected graphs one does not even distinguish source and target vertex. In the following, all graphs are undirected (but the problems can also be expressed using directed graphs). An example (undirected) graph looks like this:
a3 2
b
32
ce
d
3
1
2
f
g
• instance: a graph G = (V, E) with weighted edges E, two vertices v1 and v2
• question: What is the shortest path from v1 to v2 in G?
4Actually they won several awards, among them the G ̈odel Prize and the Fulkerson Prize in 2006.
5all from the Indian Institute of Technology Kanpur
6usually called AKS-algorithm according to the initial letters of the surnames
4
6 4
⃝c Bernhard Reus, Sussex University 2018–21 Limits of Computation
The shortest path from a to g in the graph depicted above, is a → d → g with length 5. The famous “Floyd-Warshall” algorithm listed below does find a shortest path in O(|V |3). It uses “dynamic programming”, that means it stores intermediate results. Input is a weighted graph G = (V,E) where each edge (u, v) has a weight w(u, v).
for each v in V do
for each w in V do
if v=w
then dist[v][v] := 0 // loops have no distance
else dist[v][w] := MAXINT // any other distance initially very large
end if
for each edge (u,v) in E
dist[u][v] := w(u,v) // the weight of the edge (u,v)
for k = 1 to |V|
for i = 1 to |V|
for j = 1 to |V|
if dist[i][j] > dist[i][k] + dist[k][j]
then dist[i][j] := dist[i][k] + dist[k][j]
end if
One can easily see that the first nested loop runs in O(|V | × |V |), the second one in O(|E|), and the third nested one in O(|V | × |V | × |V |). Since E ⊆ V × V we have that |E| ≤ |V | × |V |. So the dominating factor in the runtime is the last nested loop and thus the runtime of this algorithm is O(|V |3).
16.4.2 Finding maximal matchings in a graph
A matching in a graph is a set of edges such that no two edges in the set share a common vertex. Often the graph is bipartite, that means its vertices can be divided into two disjoint sets of nodes A and B, such that nodes in A (and B, respectively) are not connected and the edges of the graph always connect a vertex from A with a vertex from B. If you want to match up pairs of competitors from two teams for a competition, for instance, you would have edges between pairs of vertices that represent members of different teams. Since each competitor is supposed to have only one opponent, no two edges in the matching should share a vertex. The picture below shows two matchings for the same bipartite graph (where the different set of vertices are coloured yellow and purple, respectively). The matching of size 2 on the left hand size is highlighted in red, and the matching of size 3 on the right hand side is highlighted in blue. Indeed, three is the largest size matching for the given graph.
5
⃝c Bernhard Reus, Sussex University 2018–21 Limits of Computation
• instance: a graph G = (V, E);
• question: What is the largest matching in G?
A famous algorithm to compute maximal matchings is the “Blossom”-algorithm by Edmonds that is in O(|V |4).
That there is an algorithm with polynomial time bound (in the given strong sense regarding logarithmic size) has only be shown in 2002 in a famous (award- winning) result by: Manindra Agrawal, Neeraj Kayal, Nitin Saxena called “PRIMES is in P”. The algorithm7 they have come up with apparently is “beautiful”8. Note that the “simple-minded” primality test (also called “trial division”) that you might have learned already at school – namely to divide the given number n by all odd numbers up to the square root of n – has a complex- ity of O(2n/2) if we consider the input number represented as a binary. This is not polynomial.
16.4.3 Min-Cut & Max-Flow
A very popular problem in Operations Research is the widely studied optimi- sation problem called Max-Flow problem. It is a specific network flow problem defined as follows:
Definition
• instance: a weighted directed graph G = (V,E,w) (encoding a flow network where w(u, v) ∈ Z describes the maximum capacity of flow from nodeutonodev),asourcenodes∈V andasinknodet∈V.
• question: What is the maximum flow from s to t in G ?
This problem can be solved by the Ford-Fulkerson algorithm. The complex- ity of this algorithm is O(|E| × maxflow) where maxflow is the maximum flow of the network.
Definition A cut in a flow network graph G = (V, E, w) with source s and sink t is a set of edges S ⊆ E whose removal from E disconnects s and t. This can
7usually called AKS-algorithm according to the initial letters of the surnames 8References to articles about this result are given on our StyDir website.
6
⃝c Bernhard Reus, Sussex University 2018–21 Limits of Computation
be equivalently viewed as a partition of the nodes V into two disjoint sets A and B such that s ∈ A and t ∈ B. The capacity of a cut is the sum of the capacities of the edges in the cut.
The Min-Cut problem requires to compute the minimum capacity of flow that one needs to disconnect in order to completely stop any flow from source to sink in the given network.
Definition
• instance: a weighted directed graph G = (V,E,w) (encoding a flow network) where w(u, v) ∈ Z describes the maximum capacity of flow from nodeutonodev,asourcenodes∈V andasinknodet∈V.
• question: What is the cut with minimum capacity for the given flow network?
Theorem Let G with source s and sink t be a flow network. The maximum flow is equal to the capacity of the minimum cut.
Applications of this problem basically occur wherever networks occur: In a computer network, one may wish to route as many packets as possible. In transportation one may wish to send as many trains as possible, where tracks have certain limits on the number of trains per any given time. Similar appli- cations arise for road or phone networks. For more about this problem and its applications.
Example The graph below shows a flow network as a graph. s
23
23
11 31
45
23
t
Figure 1: A flow network as graph
The labels on each directed edge denote capacities. The network’s source
node is s and its sink node is t, respectively. The same network is depicted 7
⃝c Bernhard Reus, Sussex University 2018–21 Limits of Computation
again, but edges are now labelled with their maximum flow (in red) instead of their capacity. It is obvious from this picture that the maximum flow is 4. One can also see that the minimum cut is 4. To completely disrupt the flow
s
22
23
11 11
45
22
t
Figure 2: Max-flow for the network on the left
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 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.
16.4.4 The 7 bridges of K ̈onigsberg a.k.a. The Postman Problem a.k.a. Eulerian circuits
Legend has it that Frederick the Great of Prussia once had to host a bunch of international dignitaries whom he wanted to show the beauty of the city, first and foremost the seven bridges across the river Pregel. He thus asked the Swiss- born mathematician Leonhard Euler (1707–1783) to compute a tour across all seven bridges that visits each bridge exactly once. A tour of course ends up where it started.
8
⃝c Bernhard Reus, Sussex University 2018–21 Limits of Computation
In the above image the river is coloured blue and the bridges red.
Euler abstracted away from the concrete layout of the river and bridges by using a graph where the vertices represent the various land masses (separated by the river) and the edges represent the bridges9. The land masses in the above image are marked green and numbered 1–4 such that the resulting graph looks
like this
1
24
3
Euler could show that there was no such tour possible by proving a general 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.
A variation of this problems, where the length of the route is also important, is the so-called (Chinese10) 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 in the graph just like for the Bridges problem above.
• instance: a graph G = (V, E)
9thus inventing the field of graph theory on the fly
10due to Chinese scientist and author Kwan Mei-Ko who seemed to have introduced the
term Postman problem
9
⃝c Bernhard Reus, Sussex University 2018–21 Limits of Computation
• question: is there a cycle in G that visits each edge (or “street”) exactly once (in other words, is there an Eulerian cycle) ?
The “standard” algorithm for finding an Eulerian circuit is “Fleury’s algo- rithm” that is in O(|E|2). But there are algorithms with even better complexity as well, like “Hierholzer’s algorithm” which runs in O(|E|).11
There is also the “Route inspection problem” which is like the Postman Problem, just that you are allowed to visit an edge more than once. In this case one is interested in the shortest tour that visits each edge at least once.
16.5 Linear Programming
Consider the following problem of solving linear inequalities12. It is so general that it has an unlimited number of applications. Formally it can be described as follows:
Definition
• instance: ⃗x is a n-vector of positive (real) variables, ⃗x ≥ 0 and ⃗c is column vector, such that A⃗x ≤ ⃗b where A is an m × n matrix of integers13 , and ⃗b is a row vector of integers of length m.
• question: maximize ⃗cT · ⃗x
Here is a simple example of an application of Linear Programming:
Suppose that a farmer has a piece of land, say A km2 large, to be 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 required in different amounts per unit area for wheat (F1,I1) and barley (F2, I2). Let P1 be the price of wheat, and P2 the price of barley, each per km2. The areas planted with wheat and barley are denoted x1 and x2 (in terms of km2), respectively. The farmer would like to optimize the income, and needs to decide how much wheat or barley to plant. This can be expressed as a linear programming problem as follows:
P1 × x1 + P2 × x2 x1 + x2
F1 × x1 + F2 × x2 I1 × x1 + I2 × x2
≤ A ≤ F ≤ I
optimize revenue total area constraint fertilizer constraint insecticide constraint
which gives rise to the following instance of the Linear Programming Problem: A 1 1
⃗c=(P1P2) ⃗b=F A=F1 F2 I I1I2
11Both algorithms are famous and can be easily found on the Internet or in textbooks.
12Some Computer Science students may know this problem from Discrete Mathematics or Operations Research.
13It has m rows and n columns.
10
⃝c Bernhard Reus, Sussex University 2018–21 Limits of Computation
The best performing algorithm on average for Linear Programming is the simplex14 algorithm (also known as simplex method), discovered by George Dantzig, often cited as one of the top 10 algorithms of the 20th century. It does not run in polynomial time though. Leonid Khachiyan was the first to prove that Linear Programming is in P. His algorithm was, however not very efficient. Karmarkar improved the algorithm in 1984. His algorithm runs in On3.5L2 ln L lnln L where n is the number of variables and L is the size of the entire input (in bits). This is On2.5 times better than Khachiyan’s original algorithm.
Linear Programming is quite generic and can thus be applied to many real world problems. It plays an important role in many applications in transport, matching, and planning problems (economics). It can be used, for instance, to solve Min-Cut. Interestingly, and maybe surprisingly, a seemingly innocuous change to the Linear Programming Problem, namely restricting the solutions to be integers, leads to a much harder problem that we will discuss in the next chapter, the so-called Integer (Linear) Programming Problem.
17 Common Problems not known to be in P
In this section we present another set of useful/famous problems. However, this time we don’t know (yet) whether they are in P. Nobody has found algorithms yet that solve (decide) those problems with a polynomial (worst case) time bound.
For all these problems one can still easily find a decision procedure, for instance implementing some kind of “brute force” generate-and-test strategy at the cost of generating at least exponentially many solution candidates. Those algorithms clearly do not have a polynomial time bound. We will see later that we can test in polynomial time, however, whether candidate solutions are actually solutions.
17.1 The Travelling Salesman Problem (TSP)
The Travelling Salesman Problem has been mentioned in the introduction of this module already. It was first defined by the Irish mathematician (physicist and astronomer) W.R. Hamilton and the British mathematician Thomas Kirkman in the 19th century. As a mathematical problem it was defined in 1930 by Karl Menger. The name “Travelling Salesman Problem” was apparently introduced by American Hassler Whiteney. The origin of TSP lies with Hamilton’s Icosian Game, which was a recreational puzzle based on finding a Hamiltonian cycle, kind of a Sudoku of the 19th century, so to speak.
We now present TSP in “decision problem” form.
14In geometry, a simplex is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions: a k-simplex is a k-dimensional polytope which is the convex hull of its k + 1 vertices. The simplex algorithm uses a simplex to describe the solution space (“feasible region”) and then “runs” along the edges to find the best corner.
11
⃝c Bernhard Reus, Sussex University 2018–21 Limits of Computation
• instance: a road map of cities with distances – i.e. a graph G = (V, E) – where vertices are cities and edges are roads with weights attached denot- ing the length of the edge/distance, cities A and B, and a positive natural number k
• question: is it possible to take a trip from A to B that passes through all cities such that the resulting trip has a length that is not greater than k?
This problem is important for haulage companies or any company that has to distribute goods to many cities (places). Saving miles means saving time and fuel, thus money.
But note that it also is important for chip and other manufacturing processes. It pays off to find the shortest path for a tool, e.g. soldering equipment, to move during a production process. In the latter examples cities correspond to soldering points and edges to the potential moves of the soldering iron. As subproblem it also appears in the DNA sequencing problem (cities are DNA fragments).
Let us revisit the issue of solving this problem by a “brute-force” generate- and-test strategy. Assume we have n cities, then there are (n−1)! many round
2
trips possible (ignoring direction clockwise/anti-clockwise). But factorial num-
bers are even worse than exponentials. According to Sterling’s formula one can
approximate large factorial numbers as follows: n! ≃ √2π·n·(n)n. So n−1! √nen
is of the order O( n · n ) which is even worse than exponential growth O(k ). Note that if one applies ideas from Dynamic Programming one can cut down the time for a simple-minded search to exponential time. So algorithms that run in exponential time are indeed known for TSP, i.e. TSP is in EXP.
But this does not mean that for a small number of cities the brute-force approach can’t work: for 5 cities there are only 12 possible tours, for 8 cities we have already 20,160 possible tours. However, it won’t work for a larger numbers of cities: for 20 cities we have over 60,000 trillion tours. And if you have more than 70 cities you have definitely more possible tours than there are atoms in the known universe.15
Note that ignoring the distances, a path through all vertices from A to B is also called a Hamiltonian path. Accordingly, a tour is called a Hamiltonian tour. Again, like with Euler circuits, there is thus an abstract graph problem behind the more “applied” salesman-packaging of the problem.
15One usually calculates between 1078 and 1080 atoms in the known universe. In the “J” series of the BBC panel game quiz show “QI” (Quite Interesting), host Stephen Fry mentioned a fact about 52!, the number of possibilities you can shuffle a pack of (poker) cards. The number is so big (around 8·1067) that it is unlikely that anybody who shuffled a deck of cards before produced the same order of cards in the entire history of humanity! This requires, of course, that the deck is shuffled properly, but apparently 4 decent shuffles suffice. And of course, it just expresses an extremely low probability. So when Fry introduced his shuffling of a deck with the words “I’m going to do something that has never been done by any human being since the beginning of time.” he actually isn to quire right, he should have said “that has very very unlikely been done by any human being before.”
12
⃝c Bernhard Reus, Sussex University 2018–21 Limits of Computation
But please note the difference between the Travelling Salesman Problem and the Postman Problem, both request shortest tours, but in the first case every city (i.e. vertex in the underlying graph) needs to be visited once whereas in the second case every road (ie. edge in the underlying graph) needs to be visited once.
Note that the TSP can be generalised to multiple salesman, the resulting problem is then known as Vehicle Routing Problem.
17.2 The Graph Colouring Problem
How many colours do we need to colour a map such that no adjacent counties (or countries) have the same colour16. Well, this depends on the map, but in any case we never need more than 4 colours, even if some countries have many more neighbours. That 4 colours are always enough for a map is a famous result (The 4-colour theorem) proved by K. Appel and W. Haken in 197717, but has been already observed by Englishman Francis Guthrie in 1852.
Now maps can be seen as special graphs (planar graphs) where vertices are countries and edges between countries exist if the two countries have a common piece of borderline. This is an abstraction process similar to the step Euler made from the bridges of Ko ̈nigsberg to a graph.
Therefore, we can formulate the above colouring problem for maps as a more general problem about colouring of graphs:
Definition
• instance: a graph G and a number K of colours to be used where K ≥ 3
(otherwise it is easy).
• question: using only k colours, can one colour graph G in such a way that each pair of adjacent nodes (connected by an edge) is coloured differently?
Again this problem appears quite often in practice in various disguises. It crops up any time one wishes to assign certain limited resources that conflict with each other. In compiler construction registers need to be allocated to variables, the question how many registers you need is a version of the k-colour problem. Assigning channels (be it for network traffic or for air traffic) is like the k-colour problem; conflicting or interfering variables (compilers)/planes/radio stations share a common edge. The number of colours needed then corresponds to the maximal number of resources (registers to store variables in compilers, channels to deal with plane traffic or frequencies) needed at any time to meet the requirements.
Note that the above problem for planar graphs (maps) is only non-trivial for k = 3.
16in other words: countries that share a border need to have different colours
17“Every planar map is 4-colourable”, Illinois J. Math. 21. The proof by Appel and Haken was the first proof of a major theorem that used computers that actually computed parts of the proof which had to deal with many different cases and combinatorial problems. It was therefore initially not trusted by everyone. In 2004 a fully machine-checked proof of the 4-colour theorem has been carried out.
13
⃝c Bernhard Reus, Sussex University 2018–21 Limits of Computation
17.3 The 0-1 Knapsack Problem
Consider the problem of packing a knapsack or a container with items such that a certain capacity of the container is not exceeded, optimising at the same time the value of the packed items. As a decision procedure we replace the optimum packing with one where the value of the packed items is above a certain threshold.
Definition
• instance: a vector of n positive integers, representing the sizes, wi (1 ≤ i ≤ n) of the items, a natural number, representing the capacity or total weight of the container (knapsack), W, a vector of n positive integers, representing the profits (or values) of the items, pi (1 ≤ i ≤ n), and a natural number K
• question: Is there a way a subset of the n items can be packed (stored) in the container (knapsack) such that their profit adds up to at least K, without exceeding the total capacity W? This can be expressed by two inequalities and a boolean vector xi (1 ≤ i ≤ n), i.e. each xi is either 0 or 1, indicating whether item i is in the container (1) or not (0):
nn
wi × xi ≤ W pi × xi ≥ K i=1 i=1
Again, this finds many applications in practice: consider truck loading, or any form of capacity planning. The so-called Bin-packing Problem is like Knapsack but it uses more than one container.
There are actually quite a number of similar problems known in the litera- ture18 .
The Knapsack Problem has a special status among the problems mentioned in this section. One might think that there is actually a polynomial time algo- rithm that solves it since one can prove the following result:
Proposition Any instance of the 0-1 Knapsack Problem can be solved in On2 × pmax, where n is the number of items and pmax is the largest profit value.
Proof We again apply the concept of dynamic programming produce a n×pmax matrix V of integers where V (i, v) denotes minimum weight of a selection among the first i items with a total profit that is at least v. This matrix can be computed by initialising V(0,0) := 0 and V(0,v) = ∞ for all 0 ≤ v and then computinginanestedloop: V(i,v):=min{V(i−1,v),wi+V(i−1,v−pi)}for all1≤nand0≤v≤ipi. Thesecondterminthemaximumisonlydefined if pi ≤ v. In cases where it is not defined V(i,v) is simply set to V(i−1,v). Matrix V can be clearly computed in time O(n × i pi). The size of the optimal
18Bounded Knapsack Problem, Multiple-Choice Knapsack Problem, Multiple Knapsack Problem, Subset-Sum Problem, Change-Making Problem and so on.
14
⃝c Bernhard Reus, Sussex University 2018–21 Limits of Computation
solution, v∗, is the largest v such that V (n, v) ≤ W . The answer for the decision problem is “yes” if, and only if, v∗ ≥ K.
Is the above result not a contradiction to the claim that Knapsack is not known to be in P? The algorithm runs in time On2 × pmax. We need to look at the size of the input altogether. We measure the size of integer numbers in terms of the digits needed to represent them. The input of the algorithm consists of 2n numbers for weight and profit, plus two more numbers W and K. One can assume that all the weights are smaller than W. Then the input size is (log2 W)×(n+1)+(log2 pmax ×n)+log2 K which is O(n × (log2 pmax)). As runtime is On2 × pmax = On2 × 2log2 pmax , it follows that runtime is exponential in the size of the input and the above algorithm does not run in polynomial time. It would run in polynomial time if all input numbers of the problem were represented in the unary number system. This example shows how important it is to be precise about how the input size is measured. For reasonably small instances of numbers, however, the above mentioned algorithm based on dynamic programming does give good results.
17.4 How to deal with those problems in practice
There are, of course, many more problems of which we don’t know whether they are polynomial. Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman is a classic book that lists many problems of that kind.
Although nobody has found any algorithms for these sorts of problems that run in polynomial time, they need to be dealt with on a daily basis in practice. If the input is small, a brute-force approach might work. If the input gets bigger, maybe some clever branch and bound techniques and other heuristics-based approaches do allow the solution of the problem for slightly bigger input.
One might think that not requiring the optimal solution but an approxi- mation of the optimal solution makes the problem easier to solve, maybe to an extent that it becomes decidable in polynomial time. Alas, for most of the problems that yet have resisted polynomial time solutions, this is not the case, at least not unless we change the problem.
Other approaches of how to “ease the pain” will be discussed in Chapter 20.
18 The One-Million-Dollar Question
Since nobody could show yet that the second group of problems discussed above are in P. The fact that they are in EXP (the class of problems decided by programs with exponential time bound) or in classes with even larger time bounds than kn (like n!) just means that decision procedures with very bad asymptotic complexity are known.
In order to get a better “grasp” of those problems mentioned, we define a new complexity class. It will turn out that the question whether this new class
15
⃝c Bernhard Reus, Sussex University 2018–21 Limits of Computation
and P describe the same class of problems is a big open question, with a one- million-dollar price awarded for it. Whatever the answer is, whether the classes are equal or not equal, a proof will be required. But we will get back to this soon.
18.1 The complexity class NP
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 procedure is known, have something in common: namely that one can check whether a given candidate solution is actually a solution in polynomial time.
“In theory it is much harder to find a solution to a problem than to recognize one when it is presented.”
Stephen A. Cook
A program that can perform such a check is a “verifier”. We thus define:
Definition of Verifier: A L-verifier for a problem A ⊆ {0, 1}∗ is a L-program p (that always terminates) such that
∗L∗ A={d∈{0,1} | p (d,c)=trueforsomec∈{0,1} }
or in other words
d∈Aiff p (d,c)=trueforsomec∈{0,1} }
L∗
for all d ∈ {0, 1}∗ Program p is called a polynomial time L-verifier if its running
time in the length of just d is polynomially bounded, in other words timeLp(d,c) ≤ f(|d|) for all d
for a polynomial f. In this case, c is called the certificate used to verify that d is in A and c may be different for different instances d.
Note how this weakens the notion of a decision procedure for A. The decision procedure does not need a certificate. The certificate acts as a kind of “oracle” as it is existentially quantified and does not have to be produced by a program. For optimisation problems, this means it can encode a solution, that the program does not have to find. We will see this further below in Section 18.6.
In analogy with the definition of TIME we can now define a class of prob- lems based on their verifiers:
Definition
1. The class of problems L-verifiable in time f is:
NTIMEL(f) = {A ⊆ {0,1}∗ | A has an L-verifier p ∈ Ltime(f) }
2. NPL is the class of problems that have polynomial time L-verifiers, or in other words, NPL = {A ⊆ {0, 1}∗ | A has an L-verifier p ∈ Lptime }
16
⃝c Bernhard Reus, Sussex University 2018–21 Limits of Computation
3. NLINL = {A ⊆ {0,1}∗ | A has an L-verifier p ∈ Llintime } 4. NEXPL = {A ⊆ {0,1}∗ | A has an L-verifier p ∈ Lexptime }
Now, why is the class called NP? The reason is that this class can be defined differently. And traditionally, it has been defined with the help of nondetermin- istic Turing machines. If Turing machines are given in the “classic” style as state transformers (extensions of automata) then they appear when the transi- tion function is actually a transition relation. For the machine program style presentation given earlier one simply adds a non-deterministic program instruc- tion. This will be explained in the next subsection.
18.2 Nondeterministic Programs
For the machine-like models of computation where programs are lists of labelled instructions we define a new non-deterministic instruction:
l: goto l1 or l2 with semantics as follows:
(l,σ)→(l1,σ)if Il= gotol1 orl2
(l,σ)→(l2,σ)if Il= gotol1 orl2
So now there are two possible successor configurations when executing goto l1 or l2. Instead of a sequence of configurations we obtain a branching tree of configurations. Whenever there is a goto l1 or l2 instruction executed we obtain two new branches where the computation continues either at instruction l1 or instruction l2. Of course both branches might lead to completely different computations and outcomes. Some might not even terminate.
In order to introduce non-determinism into WHILE and WH1LE we add a further command that has the same effect as the nondeterministic jump above:
choose C1 or C2
with the following semantics
chooseC1 orC2 ⊢σ→σ′ ifC1 ⊢σ→σ′ or C2 ⊢σ→σ′
And this means that for a certain C and a certain store σ we may now have more than just one σ′ for which C ⊢ σ → σ′ holds. If we have non-deterministic programs then we cannot write any longer
L
in other words the semantics of computation models has not any longer a functional type
L
: L-data → L-data⊥ 17
p (d) = e
⃝c Bernhard Reus, Sussex University 2018–21 Limits of Computation
since there is no unique result any longer. Instead the semantics is now a relation between input and output.
L
⊆ L-data × L-data⊥
We will therefore have to redefine the class of problems decidable by non- deterministic programs within a given time bound. Instead of “decided by” we use the term “accepted by” (pointing thus out that a nondeterministic program is used).
Definition of accepting input: A nondeterministic L-program p accepts input L
d if (d), true) ∈ p . The set Acc(p) ⊆ L-data, called the set of data accepted by p, is defined as follows:
Acc(p) = {d ∈ L-data | p accepts d}
Note that it is sufficient to have one accepting execution sequence, this kind of nondeterminism is therefore called “angelic”19 Due to the nature of our nondeterministic commands in programs we do not need to specify how such accepting sequences can be obtained. The right sequence is, so to speak, “guessed” any time there is a nondeterministic instruction executed. Since we do not have any influence on the guesses they can be considered as if the execution is “flipping a coin.” Since for acceptance of input we only require the existence of one accepting sequence of which we measure the time, we can consider the nondeterministic choices be made in a “magic” way such that we obtain an accepting sequence. Moreover, next we will define time measure for nondeterministic programs in a way such that we can assume that the choices produce a minimal accepting sequence with respect to runtime.
18.3 Measuring the runtime of nondeterministic programs
The next problem that occurs is that we need to change the definition of run- time bounds for nondeterministic programs since we now have more than one execution sequence. Analogously to the input/output behaviour one generalises the runtime usage measure time form a function to a relation
Definition of runtime for nondeterministic programs: Let p be a nonde- terministic program. The time usage relation for a nondeterministic L-program p is of type
time ndLp ⊆ L-data × N⊥
which measures the time for each linear execution sequence (for a fixed number of outcomes for any choice instruction) according to the old definition given in Chapter 12. Then a time measure function for nondeterministic programs can be defined for the above relation as follows:
timeLp (d) = min{ t | (d, t) ∈ time ndLp such that p accepts input d }
19The kind of nondeterminism that corresponds to requiring that all computation sequences
need to be accepting is called “demonic” instead.
18
⃝c Bernhard Reus, Sussex University 2018–21 Limits of Computation
So the runtime of a nondeterministic program p is the shortest length of an accepting path in the tree of configurations, so the minimal possible time it takes to accept the input. Using the above definition gives one another way to define the class NPL, namely as the class of problems accepted by a nondeterministic L-program with a polynomial time bound (according to the above).
Now you might wonder what happens if there are no accepting sequences whatsoever for nondeterministic program p with input d. Then the above defi- nition yields timeLp(d) = min ∅ which usually is defined as +∞. Since our time functions have to have results in N⊥ we instead define timeLp(d) = ⊥ if p does not have any accepting sequences for input d. Note that this means all sequences are either non-terminating or produce a result that is, however, false.
In the reminder of this Chapter we however will use the simpler definition of NP using verifiers with one exception.
18.4 Some important basic facts about NP
The first observation is that P is contained in NP:
Proposition PL ⊆ NPL.
Proof Let A ∈ PL. 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. We already know that p runs in polynomial time so it is also a polynomial verifier. As mentioned at the beginning of this chapter, the reason for the N in NP is the following Theorem:
Theorem: A ∈ NPTM if, and only if, A is decided by a nondeterministic Turing machine (NTM) with polynomial time bound.
Proof Sketch The NTM simulates the verifier by guessing the certificate non- deterministically. For the reverse direction, the deterministic verifier simulates the NTM by using the certificate to determine the guesses of the simulated ma- chine.
Similar theorems can be shown for other notions of computations we dis- cussed earlier.
So “NP” stands here for Nondeterministic Polynomial, as the problem is accepted by a nondeterministic polynomially bounded program (e.g. Turing machine program).
It should be pointed out, first of all, that without any further time bounds the problems (languages) accepted by a nondeterministic Turing Machine p, Acc(p), is just recursively enumerable, in other words semi-decidable, in the previously used sense. So the additional time bound is necessary to justify the term “decidable” for problems of the form Acc(p). One might wonder therefore, why it should be ok to just consider the runtime of accepting sequences and why we do not require the nondeterministic program to terminate and, while we’re at it, even more require the program to return false in all sequences when the input is not accepted.
19
⃝c Bernhard Reus, Sussex University 2018–21 Limits of Computation
The answer for both relies on the following fact: For any nondeterminis- tic program that accepts a set A in time bounded by f, we can write another nondeterministic program that accepts A but cuts off all non-accepting compu- tations sequences after f(|d|) steps (like the efficient timed universal program did) and returns false. This program will need some extra steps but overall the runtime of the new program will still be polynomially bounded if f was a polynomial. So as far as NP is concerned, it does not matter what happens in non accepting paths of the nondeterministic program. This was discussed in detail in Question 2 on Exercise Sheet 10.
18.5 Robustness of NP
We answer two questions here. Firstly, can nondeterministic programs solve problems that deterministic programs can’t solve? Secondly, does it matter which language we enrich by nondeterministic commands (so can we solve more problems with nondeterministic Turing machine programs than we can solve with, say, nondeterministic While-programs)?
The answer to the first question is no. The Church-Turing thesis still holds also for nondeterministic machines and models. To see this one only needs to compile a nondeterministic program into a deterministic one. This can be done by the concept called “dove-tailing”20. We run all the different possible com- putation 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 be many nondeterministic commands in a pro- gram the tree of possible transition steps can branch quite enormously, in the worst case after n steps there could be 2n different execution branches. This means that the runtime of this interpreter will be exponentially slow (in the number of nondeterministic jumps taken). By partially applying the interpreter to the program in question we get a new program that is now deterministic. Note that the exponential slow-down in the simulating deterministic program is actually the “intended motivation” for using non-deterministic programs in the first place.
The answer to the second question is also no. Analogously to the determin- istic case (P) we get the following:
Theorem Aside from data-encoding issues
NPTM = NPSRAM = NPGOTO
The proof is similar to the P version in the deterministic case, the only difference is that for NP we have to compile the verifier rather than the decision procedure.
20We have used that in one of the exercises to show that if a set and its complement are both semi-decidable then the set is already decidable. The “dove tail” is split and the computation we do needs to be split up into all those potential computations (in a lock step way in order to avoid running gin to a non-terminating computation).
20
⃝c Bernhard Reus, Sussex University 2018–21 Limits of Computation
18.6 All our “hard” problems are in NP
Theorem The Travelling Salesman Problem, the Graph Colouring Problem21, and the 0-1 Knapsack problem, the Integer Linear Programming Problem are all in NP.
Proof: The definition of NP makes it relatively easy to define a deterministic program that with the help of a certificate verifies the existence of a solution in polynomial time. The certificate is simply the (encoding of the) solution itself:
1. The certificate encodes a candidate for the solution (i.e. a path, colouring or packing of the knapsack, depending on the problem).
2. Verify that the encoded candidate solution has the required property (i.e. tour has total length ≤ K, scheduling meets all constraints, selected items in the knapsack add up to knapsack size etc.).
3. This verification needs to be possible in polynomial time in terms of the size of the problem (e.g. a graph with a number as quality measure). This has to be shown for every problem individually. For the given ones, it should be again obvious that the verification can be done polynomially in the size of the problem description. For instance, for the TSP problem – where the input of the verifier is a graph G = (V,E) and a number K – one needs to check that a given candidate for a tour visits all vertices which is done in time O(|V |2), that start and end are the same vertex, which can be done in time O(1), that for each itinerary from v1 to v2 there is actually an edge, which can be done in time O(|V | · |E|), and that the sum of distances travelled is smaller or equal K, which can be done in time O(|V |). So clearly, putting all these checks together, the verification runs in polynomial time in the size of the input which for a wieghted graph G = (V, E, w) with number K is |V | + |E| + log2 K + e∈E log2 we.
18.7 The biggest open problem in (theoretical) computer science
The big open problem actually is whether NP is the same (class) as P. P=? NP
If P and NP were indeed the same class, then for all the “hard” problems we discussed in Chapter 17 – for which nobody has found a polynomial time algorithm to date – there would actually have to exist such a polynomial time algorithm. This open problem has attracted much attention. The Clay Math- ematics Institute that offers prize money of one million dollar for a (proven correct) answer to seven “Millennium Problems”, has included P=NP? as one
21with k ≥ 3
21
⃝c Bernhard Reus, Sussex University 2018–21 Limits of Computation
of those seven22 problems despite the fact that it is, strictly speaking, not (just) a mathematical problem but one of computation.
Every few years somebody makes a valid effort and claims to have solved P = NP? (usually attempting to prove P ̸= NP) but so far all those attempts have been quickly refuted by the experts in the field23.
Fact is that still nobody knows whether P = NP. We will see shortly that the answer to this question hugely affects computer science as we know it. In a way, we’ve already noticed this a bit when we observed that for none of the problems in Section 16 we know any polynomial time algorithms. Most computer scientists think that P is not equal to NP. Scott Aaronson (MIT) puts it like this24:
“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 reason- ing power of Archimedes or Gauss.”
Moreover, the other Millennium Problems could then most likely be solved by a program.
22Note that one of then, the Poincar ́e Conjecture has been proved in 2002 by Russian mathematician Grigoriy Perelman who was eventually awarded the Millennium Prize from the Clay Institute in 2010 but declined the prize, as he declined many other prestigious awards before.
23The last such proof attempt that received wide press coverage was submitted in August 2010 by Vinar Deolalikar from HP Labs (see Canvas website links).
24Scott Aaronson: “Quantum Computing since Democritus”, Cambridge University Press, 2013.
22