19. NP-Completeness#
Learning Objectives#
After completing this chapter, you will be able to:
Define a metric graph.
State the traveling salesman problem and know how to check solutions.
Understand the idea of a polynomial time reduction from one problem to another.
Recall the satisfiability (SAT) problem.
Conceptually understand the idea of NP-completeness.
1. Metric Graphs#
In the previous section we introduced the idea of a graph, and mentioned the idea of a metric graph. A metric graph is a graph where there is a number assigned to each edge. Sometimes these numbers are restricted to be non-negative, and could be viewed as distances or costs.
For example, below is a diagram representation of a metric graph, where the vertices are labeled with letters and the edges are assigned numbers. You could interpret these numbers as distances, and say, for example, the distance between \(a\) and \(b\) is \(4\), while the distance between \(e\) and \(z\) is \(1\).
2. The Traveling Salesman Problem#
Suppose you were a salesman and there were a number of cities where you needed to make your sales calls. Some of these cities are connected by roads, and each of these connecting roads has some corresponding distance. Assume it’s always possible to find a sequence of roads from one city to another. You could formulate this as a connected metric graph, with the cities being vertices and the edges being roads with their numbers being distances. The traveling salesman problem is the problem of figuring out the optimal circuit through the connected graph, where “optimal” here means the path that minimizes the total distance traveled. Note that the metric doesn’t necessarily need to be distance, ande could easily be something like transit time or cost that you might also want to minimize.
A variant on this problem is the question of whether there’s a circuit below a certain distance or cost. For example, suppose your metric is cost, your travel budget is \\(2,000, and you want to know whether there is a circuit that hits every city that costs less than your budget. Note this circuit doesn't necessarily need to be the overall most cost efficient circuit - it just needs to be one under \\\)2,000.
This problem of determining whether, for a given metric graph and value, there is a circuit through the graph with distance less than that value, is in NP. This is pretty straightforward. If you’re provided with a metric graph, a value, and a sequence of vertices in the metric graph, you can quickly check whether that sequence is a circuit and if the total distance of that circuit is below that value. So, it’s quick to verify whether the solution is correct. However, just given a metric graph and a value determining whether there is a circuit with total distance less than that value has no known polynomial time solution. So, it’s not known whether the problem is in \(P\), and strongly suspected it is not.
3. The Hamilton Path Problem and the Traveling Salesman Problem#
In the previous section we discussed the Hamilton circuit problem, which is the problem of finding a circuit in a connected graph that visits each vertex (except the first and last one) exactly once. This problem, like the traveling salesman problem, is in \(NP\), but it’s not known if this problem is in \(P\), and strongly suspected it is not.
Suppose by some miracle you figured out a polynomial time solution to the traveling salesman problem. In other words, suppose you had a polynomial time algorithm that could determine for a given connected metric graph and value whether there is a circuit in that graph with total distance less than that value. Well, in that case you’d also have a polynomial time solution to the Hamilton circuit problem!
The reason for this is that you can translate the Hamilton circuit problem into the traveling salesman problem in a polynomial amount of time. The way you’d do this is you’d take your connected graph and convert it to a metric graph by assigning to each edge the length of \(1\). This can be done in an amount of time proportional to the number of edges, which is linear, and so definitely polynomial. Then, if there were \(n\) vertices in the graph, you’d just check whether there is any circuit in the metric graph you created of length less than \(n+1\). If the answer is yes, then that circuit would be a solution to the Hamilton path problem. If the answer is no, that would mean the original graph does not have a Hamilton circuit. As this last problem is the traveling salesman problem, if we can solve it in a polynomial amount of time, then we have a polynomial time solution to the Hamilton circuit problem.
We call this process of converting one problem into another a reduction, and if there is a polynomial time reduction from one problem a second problem, and a polynomial time solution to the second problem, then a polynomial time solution to the first problem is to reduce it to the second and solve the second. So, if you can find a polynomial time solution to a problem, you’ve not only found an efficient solution for that problem, you’ve found a solution for any other problem that can be efficiently reduced to it.
4. Logical Satisfiability#
We’re going to briefly introduce the problem of logical satisfiability here. It’s expected this is something you’ve seen before, and so this will be a somewhat terse review.
A propositional variable is a variable that can have two possible values - “true” and “false”, donoted \(T\) and \(F\). There are three operators on propositional variables, and their rules are:
\(\neg\) means negation or “not”, and the rule is that if \(P\) is true, then \(\neg P\) is false and vice-versa.
\(\land\) means conjunction or “and”, and it combines two logical propositions into one with the rule that \(P \land Q\) is true if and only if both \(P\) and \(Q\) are true, and false otherwise.
\(\lor\) means disjunction or “or”, and it combines two logical propositions into one with the rule that \(P \lor Q\) is true if and only if either \(P\) or \(Q\), or both, are true, and false otherwise.
Propositional logic statements are formed by combining propositional variables using the operators above and the rule that substatements within parentheses are evaluated first. Note you may have seen other logical operators like the implication \(\rightarrow\), but these other operators can all be translated into equivalent statements using just the three operators above. For example, the implication \(P \rightarrow Q\) is equivalent to \((\neg P \lor Q)\).
A logical statement is satisfiable if there is some assignment of truth values to its propositional variables that makes the entire statement true. We say such an assignment satisfied the statement. For example, the logical statement:
is satisfied by the truth assignment \(P = T, Q = T\). However, there is no assignment of truth values to \(P\) and \(Q\) that make the statement:
true. Therefore, the second statement above is not satisfiable.
If we’re given a logical statement and a truth assignment for its variables, it’s easy (can be done in polynomial time) to verify whether the truth assignment works to make the entire statement true. If we’re given a logical statement we can check if it’s satisfiable by checking every possible truth assignment. However, if there are \(N\) propositional variables in the statement, then there are \(2^{N}\) possible truth assignments, and checking them all one-by-one requires an amount of time that is exponential (beyond polynomial) in the number of propositional variables. In other words, whether a logical statement is satisfiable (a problem called SAT) can be verified in a polynomial amount of time, but there is no known algorithm for determining whether any solution exists that runs in a polynomial amount of time, and it’s strongly suspected no such algorithm exists. This is like the Hamilton circuit and traveling salesman problems.
5. NP-Completeness#
A remarkable result discovered in the early 1970s was that every NP problem (every problem for which a solution can be verified in a polynomial amount of time) can be reduced to a problem in SAT in a polynomial amount of time. This result is known as the Cook-Levin theroem, and it means that SAT is at least as “hard” as any other NP problem.
Now, any NP problem can be reduced in a polynomial amount of time to a problem in SAT. If SAT can also be reduced to an NP problem (like the Hamilton circuit problem on the traveling salesman problem) in a polynomial amount of time, then that means the other problem is also at least as “hard” as any other NP problem. This gives us an entire set of problems in NP that are at least as hard as any other problem in NP, and these problems are called NP-complete.
A great many NP-complete problems have been discovered, including SAT, the Hamilton path problem, and the traveling salesman problem, and more are discovered every year.
6. Does P = NP?#
Finding a polynomial time solution to any NP-complete problem would provide a polynomial time solution to all of them. It is strongly suspected that none exist. However, to date, nobody has been able to prove this, and it’s the most significant open problem in theoretical computer science. In fact, it’s such a significant open problem that when the Clay Mathematics Institute put forth a list of 7 problems for the 21st century, and placed a $1,000,000 prize on each of them, one of the seven problems was the question of whether \(P\) equals \(NP\). To date the 21st century is about a quarter of the way done, and only one of the seven problems (the Poincaré conjecture) has been solved.
7. Practice Exercises#
TK
8. Further Reading#
TK