
The theory of NPcompleteness 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 NPcompleteness have anything to say about those?
In fact, NPcompleteness does help us to understand the cost of solving functional problems, and that is what we investigate on this page.
The definition of an NPcomplete problem is based on polynomialtime mapping reductions.
For this page, we need polynomialtime 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 ≤_{p}^{t} B if A is computable in polynomial time on a Bmachine.
For our purposes, the value of a polynomialtime 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 NPhard if, for all X ∈ NP, X ≤_{p}^{t} A.
An NPhard 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 NPcomplete 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.
MinColor 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 NPhard. Each one is closely related to a known NPcomplete problem. Let's take the Maximum Clique problem (MAXCLIQUE) as an example. CP is the Clique problem.
Theorem. CP ≤_{p}^{t} MAXCLIQUE
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 MAXCLIQUE is NPhard. But it is interesting that the opposite reduction, from MAXCLIQUE to CP, can be done.
Theorem. MAXCLIQUE ≤_{p}^{t} 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.
