|
The theory of NP-completeness is only concerned with decision problems (where the answer is always yes or no.)
That appears to be necessary since nondeterminism involves evidence checking, and evidence can only be good or bad, nothing in between.
But what about problems whose answer is not yes or no? Does NP-completeness have anything to say about those?
In fact, NP-completeness does help us to understand the cost of solving functional problems, and that is what we investigate on this page.
The definition of an NP-complete problem is based on polynomial-time mapping reductions.
For this page, we need polynomial-time Turing reductions.
Recall that a Turing reduction is defined in terms of oracle machines.
Suppose that A and B are two functional problems.
Definition. Say that A ≤pt B if A is computable in polynomial time on a B-machine.
For our purposes, the value of a polynomial-time Turing reduction is that it can be used to relate functional problems, not just decision problems.
Let A be a functional or decision problem.
Definition. A is NP-hard if, for all X ∈ NP, X ≤pt A.
An NP-hard problem is at least as hard as every problem in NP, and it might be much harder.
There are optimization problems associated with several of the NP-complete problems that we have encountered. Here are a few.
Traveling Salesman Optimization Problem. Given a distance matrix, find the shortest traveling salesman tour.
Maximum Clique Problem. Given an undirected graph G, find a largest possible clique in G.
Min-Color Problem. Given an undirected graph G, color the vertices G with the fewest possible colors, ensuring that no two adjacent vertices have the same color.
Longest Path Problem. Given an undirected graph G and two vertices u and v, find a longest simple path from u to v.
All of those problems are NP-hard. Each one is closely related to a known NP-complete problem. Let's take the Maximum Clique problem (MAX-CLIQUE) as an example. CP is the Clique problem.
Theorem. CP ≤pt MAX-CLIQUE
Proof. To determine whether graph G has a clique of size at least K:
Find a largest clique in G.
Let m be the number of vertices in the largest clique.
If m ≥ K, answer yes, else answer no.
That is all we need to show that MAX-CLIQUE is NP-hard. But it is interesting that the opposite reduction, from MAX-CLIQUE to CP, can be done.
Theorem. MAX-CLIQUE ≤pt CP
Proof. We need to given an algorithm to find a largest possible clique in G, assuming that it can solve the Clique problem (a decision problem) in just one step.
Find out the size s of the largest clique in G by asking CP whether there is a clique of size 1, size 2, … until a size is reached where the answer is no.
For each vertex v in G,
G′ = the graph that you get by removing vertex v from G.
If G′ has a clique of size s, then make G = G′.
When the algorithm is finished, the remaining graph G will be a clique of size s. Examining its vertices shows which vertices of G to choose.
|