18. P and NP Problems#
Learning Objectives#
After completing this chapter, you will be able to:
Understand the mathematical concept of a graph consisting of a set of nodes and edges.
Understand what is meant by a problem that is solvable in polynomial time, a.k.a. in P.
Understand what it means for a problem to be solvable in nondeterministic polynomial time, a.k.a. in NP.
1. Graphs#
Graph is a word that might be overused in mathematics, in that it is used to describe multiple distinct ideas. But, unfortunately, natural language can be like that.
You’ve likely seen the term graph used primarily to describe a visualization of the relation between the input and the output of a function. For example, the graph of the function
looks like
However, the term graph is also used for a mathematical structure used to represents objects and their connections. This type of graph consists of objects called vertices or sometimes nodes, and connections between these vertices called edges. Stated more formally
Definition - A graph is a pair \((V,E)\) where \(V\) is a set whose elements are called vertices, and \(E\) is a set of unordered pairs \(\{v_{i},v_{j}\}\) of vertices whose elements are called edges.
It’s possible to also have graphs where the edges are ordered, so an edge “points” from one vertex to another. These are called directed graphs. It’s also possible to have graphs where there can be more than one edge between two vertices, and these are called multigraphs. Sometimes the edges are assigned numbers, and these are called weighted graphs. For the purposes of this section we won’t deal with any of these.
Graphs are frequently displayed as a collection of dots (the vertices) and lines between them (the edges). For example, the graph below has three vertices, and an edge connecting each pair.
This is called the complete graph on three vertices, and is sometimes written \(K_{3}\). If we label the vertices \(v_{1}, v_{2}, v_{3}\) then we could specify the graph as:
\(E = \{\{v_{1},v_{2}\}, \{v_{1},v_{3}\}, \{v_{2},v_{3}\}\}\)
Example - The graph represented by the image
has the set of vertices
and the set of edges
All the nodes at the “top” of this graph are connected to the nodes at the “bottom”, but none of the nodes at the “top” are connected to any of the others at the “top”, and same with the nodes at the “bottom”. This is an example of a type of graph called a complete bipartite graph, and this particular one is called the complete bipartite graph on \((4,3)\) nodes, and abbreviated \(K_{3,4}\).
The degree of a vertex is the number of edges connected to it. For example, in the graph \(K_{3,4}\) above the degree of \(u_{2}\) is \(4\), while the degree of \(v_{1}\) is \(3\).
A path in a graph is a sequence of nodes where there is an edge between any node and the next one in the sequence. For example, the sequence:
would be a path in \(K_{3,4}\) above, but the sequence:
would not be, as there is no edge connecting \(u_{2}\) and \(u_{3}\). A path that begins and ends on the same vertex is called a circuit.
We say two nodes are connected if there is a path in the graph that starts at one and ends at the other. A graph is connected if every pair of nodes within the graph are connected. Both of the graphs \(K_{3}\) and \(K_{3,4}\) above are connected. The graph below would not be, as there is no path from the node labeled \(0\) to any of the other nodes. Note the labels of each node indicate that node’s degree.
2. The Königsberg Bridge Problem#
In the 18th century the city of Königsberg in Prussia (now Kaliningrad, Russia) was set on both sides of the Pregel River, and included two large islands—Kneiphof and Lomse—which were connected to each other, and to the two mainland portions of the city, by seven bridges.
The Königsberg bridge problem was whether it was possible to devise a walk through the city that crossed each bridge only once. Many people played around with this problem and nobody was able to find a solution.
In 1736 the great mathematician Leonhard Euler published a mathematical proof that the problem was, in fact, impossible to solve. He did this by first formulating the problem as a question about a graph, where the nodes of the graph were the land masses of Königsberg, and the edges were the bridges.
The problem then became whether it was possible to find a path in the graph that traversed each edge exactly once. Euler proved that for any connected graph this is possible if and only if no more than two vertices have an odd degree. Such a traversal is now called an Euler path, and if the path begins and ends on the same vertex, it is called an Euler circuit.
Theorem - For any connected graph
An Euler path exists if no more than two nodes have an odd degree.
An Euler circuit exists if no nodes have an odd degree, a.k.a. every nodes has an even degree.
For the graph corresponding with the bridges of Königsberg, all four nodes have an odd number of incident edges, and so no Euler circuit or Euler path exists.
3. Polynomial Time (P) Complexity#
To create an algorithm to check whether a connected graph has an Euler circuit, we could try to list off all paths within the graph that don’t traverse an edge more than once, and then check whether any of them traverse each edge. This is possible, and would work, but it would be a very inefficient way to do it.
On the other hand, using the theorem above we could create a much more efficient algorithm for answering the question. If we had a connected graph represented by a set of vertices \(V\) and a set of edges \(E\) we could determine whether the graph contained an Euler circuit with an algorithm that:
Read in the vertices and created a list of these vertices where each element of the list had a corresponding count, with counts all initialized to \(0\).
Read in the edges and for each edge incemented the count of both its vertices by \(1\).
Checked whether all the vertices in the list had an even count.
For example, for the graph \(K_{3}\) above the algorithm would be given the vertices and edges as input:
\(E = \{\{v_{1},v_{2}\}, \{v_{1},v_{3}\}, \{v_{2},v_{3}\}\}\)
It would then read in the list of vertices and created a list of these vertices with corresponding counts, all initialized to \(0\):
\(v_{1}: 0\)
\(v_{2}: 0\)
\(v_{3}: 0\)
It would then read the first edge in \(E\), \(\{v_{1},v_{2}\}\), and increment the counts for both \(v_{1}\) and \(v_{2}\) by \(1\):
\(v_{1}: 1\)
\(v_{2}: 1\)
\(v_{3}: 0\)
It would then continue this process for every edge in \(E\) and at the end the list would be:
\(v_{1}: 2\)
\(v_{2}: 2\)
\(v_{3}: 2\)
As the counts are all even, the algorithm would return that, yes, an Euler circuit exists. Note that it wouldn’t explicitly find a circuit, but one examle for this graph would be \(v_{1} \rightarrow v_{2} \rightarrow v_{3} \rightarrow v_{1}\).
How much time would this algorithm take to run? Well, it would need to create an element in the list for every vertex in the graph, and then it would need to read in every edge and increment the count for two vertices, it would then need to whether each count is even. The amount of time required for the first part would be a constant multiple of the number of vertices, for the second part a constant multiple of the number of edges, and for the third part a constant multiple of the number of vertices. We could express this as:
So, the amount of time required for this algorithm would be linear (a degree one polynomial) in the number of vertices and the number of edges. We could say the complexity of the algorithm is polynomial (or, even stronger, linear) is the size (the number of vertices and number of edges) of the graph. This is an example of a polynomial time algorithm, and so we would say the complexity of the problem of determining whether a connected graph has an Euler circuit is in polynomial time, which we abbreviate as \(P\).
4. Nondeterministic Polynomial Time (NP) Complexity#
An Euler path is one that traverses every edge of the graph exactly once. A natural analog of this would be a path that visits every vertex of the graph exactly once. A path like this is called a Hamilton path, after the great 19th century British mathematician William Rowan Hamilton.
More precisely, a Hamilton path in a graph is a path that contains each vertex of the graph exactly once. A Hamilton circuit is a circuit that contains each vertex of the graph exactly once except the first one in the path, which is also the last one.
For example, the graph \(K_{3}\) has a Hamilton circuit (which also happens to be an Euler circuit):
On the other hand, the graph \(K_{3,4}\) has a Hamilton path, for example:
However, it does not contain a Hamilton circuit.
You might hope a simple algorithm like the one above for Euler circuits exists for determining whether a connected graph contains a Hamilton circuit. Perhaps surprisingly, no such algorithm is known, and its very strong suspected (but not proven!) that no such algorithm exists. More precisely, there is no known algorithm that can check whether a connected graph contains a Hamilton circuit in an amount of time that is polynomial in the size (the number of vertices and edges) of the graph. The best general algorithms all must, essentially, just go through all the possible curcuits that don’t repeat a vertex (except at the beginning and end) and check each one to see if it’s a Hamilton circuit. This isn’t very efficient, and the amount of time this takes is exponential in the size of the graph.
Now, suppose instead of determining whether a graph contains a Hamilton circuit, you instead just want to check whether a given sequence of vertices is, indeed, a Hamilton circuit. In other words, you want to verify whether a proposed solution is correct. For example, suppose you have the graph \(K_{5}\) (the complete graph on 5 vertices) below:
and you’re given the path:
How would you check whether this was a Hamilton path? Well, an algorithm for doing so might be to go through the sequence of vertices in the path, and confirm that every vertex in the graph is in the sequence, no vertex in the sequnce repeats (except at the start and end), and every arrow in the sequence corresponds with an edge in the graph. How long would this take? It would be a constant multiple of the length of the path, which would be one more than the number of vertices in the graph. In other words, the amount of time required to check whether a solution is correct would be a polynomial (linear) function of the size of the graph. So, even though we might not be able to always determine if a solution exists in a polynomial amount of time, we are able to verify whether a proposed solution is valid in a polynomial amount of time. Problems for which this is the case are in nondeterministic polynomial time (NP) complexity. Stated more formally, a problem is in NP if you can determine in a polynomial amount of time whether a solution exists if you are provided with a correct solution.
Why do we call problems where a solution can be verified in a polynomial amount of time “nondeterministic” polynomial time? Well, the basic idea is that suppose we’re using the “brute force” method of just listing out all the possible solutions and checking them one by one. As we list out possible solutions, we need to make choices. For example, suppose in the graph \(K_{5}\) above we’re trying to generate possible solutions, and we start on vertex \(v_{1}\). Where do we go from there? We could go to \(v_{2}\) or \(v_{3}\) or \(v_{4}\) or \(v_{5}\). We need to determine the next step, and if we want to explore all the possibilities, we would need to do so sequentially. On the other hand, suppose we didn’t need to determine the next step, and could explore all the possibilities simultanously. In this nondeterministic case we’d be able to list out all the possible paths much more quickly, and checking them all simultanously would only require a polynomial amount of time. In other words, if we could explore the set of possibilites nondeterministically (simultaneously) then we could determine whether a solution exists in a polynomial amount of time. If this is a bit confusing to you, don’t worry about it, just remember than NP means a proposed solution can be verified in a polynomial amount of time.
5. Practice Exercises#
Exercise 1: Prove that the graph \(K_{5}\) above has an Euler circuit and provide an example of such a circuit.
Exercise 2: Prove that any problem in \(P\) must also be in \(NP\).
Exercise 3: (Challenge) Suppose you’re given a graph as a set of vertices \(V\) and a set of edges \(E\). You want to determine whether the graph is connected. Prove that the problem of determining whether a graph is connected is in \(P\).
6. Further Reading#
“Introduction to the Theory of Computation” (Third Edition) by Michael Sipser: Sections 7.1-7.3 - Measuring Complexity, The Class P, The Class NP
“Automata Theory, Languages, and Computation” (Third Edition) by John. E Hopcraft, Rajeev Matwani, and Jeffrey D. Ullman: Section 10.1 - The Classes \(P\) and \(NP\)