P=NP?

The Traveling Salesperson Problem

Xiao Hui recently encountered a difficult problem at work. His company is developing a logistics project, and one requirement is to plan delivery routes automatically for couriers.

A courier needs to deliver packages to three customers. The distance from the starting point to each customer's home differs, as do the distances between customers. Which route delivers all three packages and returns to the start with the shortest total distance?

Xiao Hui spent a long time looking for the optimal route, but could not find an efficient solution. He is not alone: computer scientists have not discovered a generally efficient optimization algorithm for this classic traveling salesperson problem.

A salesperson must visit several cities to sell products. Starting from one city, the salesperson must visit every city and return to the starting point. Roads connect every pair of cities, with different distances between them. How should the route be chosen to minimize the total journey?

The problem looks simple, yet finding a truly efficient algorithm is difficult. The most direct approach is enumeration: list every possible route, calculate its total distance, and choose the shortest. Because the visiting orders are permutations, this approach takes $O(n!)$ time. As the number of cities grows, the required computation becomes unimaginable.

Researchers have developed improved approaches, including dynamic programming and branch and bound. Their worst-case time complexity is still exponential, however, so they do not fundamentally remove the performance problem.

The traveling salesperson problem is only one example among many problems associated with the class NP.

P=NP?

Algorithm design and analysis have an important place in computer science. Between 1966 and 2005, 50 people received the Turing Award; 10 were recognized for algorithm design, while 7 were recognized for contributions to computation theory, automata, and complexity. The P=NP? question in computational complexity theory is one of the seven Millennium Prize Problems.

Many familiar algorithms have complexities such as $O(\log n)$ for binary search, $O(n\log n)$ for merge sort, and $O(n^3)$ for the Floyd shortest-path algorithm. Each can be written as $O(n^k)$. These are polynomial-time algorithms: they solve problems within polynomial time. Such problems belong to P (Polynomial time).

People often say that a problem money can solve is not really a problem. To computer scientists, a problem that polynomial time can solve is not really a problem.

Yet many unusually difficult problems cannot, at least for now, be solved in polynomial time. Known algorithms may take $O(2^n)$ or even $O(n!)$. As the problem size $n$ grows, the amount of computation rises at a frightening rate. These are commonly discussed as NP (Nondeterministic Polynomial time) problems.

More precisely, NP is the class of decision problems whose proposed solutions can be verified in polynomial time. It does not stand for “non-polynomial” or mean “uncertain whether polynomial-time solution is possible.” We do not currently know whether every problem in NP can also be solved in polynomial time.

Some scientists believe that every NP problem can ultimately be solved in polynomial time and that we simply have not found the methods yet. Others believe that some NP problems can never be solved in polynomial time. The question P=NP? expresses this disagreement.

There is another important group within NP: NP-complete problems.

NP-Complete Problems

To understand NP-complete problems, first consider the idea of reduction.

A reduction is a transformation from one problem to another. Suppose $Q$ is the linear equation $3x+6=12$. It can be transformed into the quadratic equation $Q': 0x^2+3x+6=12$.

Problem $Q$ is no harder than $Q'$: any method that solves $Q'$ can also solve $Q$. In this situation, we say that $Q$ reduces to $Q'$.

Reductions are transitive. If problem A reduces to B, B reduces to C, and C reduces to D, then A reduces to D.

NP problems can also be related through reductions. Problems to which every problem in NP can be reduced, and which are themselves in NP, are called NP-complete. The traveling salesperson problem is commonly used as an example.

More precisely, the decision version, which asks whether a route no longer than a given limit exists, is NP-complete. The optimization version, which asks for the shortest route, is NP-hard.

If we ever find a polynomial-time algorithm for one NP-complete problem, reductions would let us solve every NP problem in polynomial time. No one has found such an algorithm, and many researchers believe none exists.

Return to the original delivery-routing problem. Because it is an engineering problem, seeking a useful approximate solution at much lower cost may be better than insisting on the exact optimum. A simple greedy method first visits the location nearest the starting point, then the location nearest that one, and so forth. Every step is locally optimal. The resulting route may not be globally optimal, but it can still be useful in practice.