A special form of the problem SS is when the sum of the whole list is equal to 2S. This subproblem of SS is called PARTITION: given a list of integers Polynomial-time many-one reducibility is a strong type of reducibility on decision problems (i.e., languages) that preserves the membership in the class P. In this section, we extend this notion to a weaker type of reducibility called polynomial-time Turing reducibility that also preserves the membership in P. Moreover, this weak reducibility can also be applied to search problems (i.e., functions). Intuitively, a problem A is Turing reducible to a problem B, denoted by The above example (c) illustrates a typical relation between a decision problem and the corresponding optimization search problem. That is, the optimization search problem is polynomial-time solvable if it is allowed to make one or more queries to the corresponding decision problem. In the following, we define oracle Turing machines as the formal model for the notion of polynomial-time Turing reducibility. A function-oracle DTM is an ordinary DTM equipped with an extra tape, called the query tape, and two extra states, called the query state and the answer state. The oracle machine M works as follows: First, on input x and with oracle function f (which is a total function on Let M be an oracle TM. Then, M defines an operator that maps each total function f to a partial function g, the function computed by M with oracle f. We write Mf to denote the computation of M using oracle f, and let A special type of oracle machines are those that only use 0-1 functions as oracles. Each 0-1 function f may be regarded as the characteristic function of a set As we will be mostly working with set-oracle DTMs, we only give a formal definition of the computation of a set-oracle DTM. We leave the formal definition of the computation of a function-oracle TM as an exercise (Exercise 2.12). Formally, a two-tape (set-)oracle DTM M can be defined by nine components A configuration of a two-tape oracle DTM is formally defined to be an element in A computation We now formally define the notion of Turing reducibility based on the notion of oracle TMs. The time complexity of a set-oracle TM can be defined in a similar way as that of an ordinary TM. The single extra rule is that the transition from the query state to either the yes state or the no state (performed by the oracle) counts only one step. Thus, for any set-oracle machine M, oracle A and any input x, The time complexity of a function-oracle TM can be defined similar to that of a set-oracle TM. A potential problem may occur though if the oracle function f is length increasing. For instance, iff can replace a query string y of length n by the answer string In addition to the notations FPg and PB, we also write The reader is expected to verify that the reductions described in Example 2.4 can indeed be implemented by polynomial-time oracle machines. It is easy to see that Let The notion of the space complexity of an oracle DTM M is not as easy to define as the time complexity. The straightforward approach is to define Based on the notion of polynomial-time Turing reducibility, we can see that many important combinatorial optimization problems are NP-hard search problems. We prove these results by first showing that the corresponding decision problems are We first introduce a general framework to deal with the approximation problems. Very often, an optimization problem Π has the following general structure: for each input instance x to the problem Π, there are a number of solutions y to x. For each solution y, we associate a value Let r be a real number with r > 1. For a maximization problem Π with the above structure, we define its approximation version, with the approximation ratio r, as follows: Similarly, for a minimization problem Π, its approximation version with the approximation ratio r is as follows: In general, the approximation ratio r could be a function r(n) of the input size. In this section, we consider only approximation problems with a constant ratio r. We first consider a famous optimization problem: the traveling salesman problem. The traveling salesman problem is an optimization problem that asks, from a given map of n cities, for a shortest tour of all these cities. The following is the standard formulation of its corresponding decision problem:Theorem 2.15
Proof
Theorem 2.16
Proof
Theorem 2.17
Proof
SUBSET SUM (SS): Given a list of integers
and an integer S, determine whether there exists a set 
such that 
.Theorem 2.18
Proof
, determine whether there is a set 
such that 
.Corollary 2.19
Proof
2.4 Polynomial-Time Turing Reducibility
, if there is an algorithm M for A which can ask, during its computation, some membership questions about set B. If the total amount of time used by M on an input x, excluding the querying time, is bounded by 
for some polynomial p, and furthermore, if the length of each query asked by M on input x is also bounded by 
, then we say A is polynomial-time Turing reducible to B and denote it by 
. Let us look at some examples.Example 2.20
), it begins the computation at the initial state and behaves exactly like the ordinary TM when it is not in any of the special states. The machine is allowed to enter the query state to make queries to the oracle, but it is not allowed to enter the answer state from any ordinary state. Before it enters the query state, machine M needs to prepare the query string y by writing the string y on the query tape and leaving the tape head of the query tape scanning the square to the right of the rightmost square of y. After the oracle machineM enters the query state, the computation is taken over by the “oracle” f, which will do the following for the machine: it reads the string y on the query tape; it replaces y by the string f(y); it puts the tape head of the query tape back scanning the leftmost square of f(y); and it puts the machine into the answer state. Then the machine continues from the answer state as usual. The actions taken by the oracle count as only one unit of time.
denote the set of strings accepted by M with oracle f (i.e., the domain of function g).
. In this case, we write MA and 
for Mf and 
, respectively. This type of oracle machine has a simpler but equivalent model: the set-oracle Turing machine. A set-oracle TM M has an extra query tape and three extra states: the query state, the yes state, and the no state. The machine behaves like an ordinary DTM when it is not in the query state. When it enters the query state, the oracle (set A) reads the query y and puts the machine into either the yes state or the no state, depending on whether 
or 
, respectively. The oracle also erases the content y of the query tape. Afterwards, the machine M continues the computation from the yes or the no state as usual.
. Similar to the ordinary DTMs, Q is a finite set of states, 
is the initial state, 
is the set of final states, Σ is the set of input alphabet, and 
is the set of tape symbols, including the blank symbol 
. In addition, 
is the query state, qY is the yes state, qN is the no state, and δ is the transition function from 
to 
.
. A configuration 
denotes that the machine is currently in state q, theregular tape contains the string 
, the tape head is scanning the leftmost symbol of y1, the query tape contains the string 
, and the tape head of the query tape is scanning the leftmost symbol of y2; the string x2 is called the query string of α. We extend the transition function δ to configurations to define a move of the machine M. Let α and β be two configurations of M. We write 
to mean that α is not in state 
and β is the next configuration obtained from α by applying the function δ to it (see Section 1.2). If 
, then we write 
if 
and write 
if 
. The computation of an oracle DTM 
on an input x is a sequence of configurations 
, satisfying the following properties:
;
, either 
or 
or 
.
of M on input x is consistent with an oracle set A, if for each i, 
, such that αi is in state 
, 
if and only if the query string in αi is in A, and 
if and only if the query string in αi is not in A. We say M accepts x, relative to oracle set A, if there exists a computation of M on x that is consistent with A and whose halting state is in F. We define 
accepts x relative to 
.Definition 2.21
is defined to be the length of the halting computation of M on x relative to A. We then define 
. We say that 
for some function g if for any oracle A and any n ≥ 0, 
. Note that the measure 
is taken over the maximum of 
over all possible oracle sets A. In the applications, we often find this measure too severe and consider only 
for some specific set A or for some specific group of sets A. An oracle TM M is called a polynomial-time oracle Turing machine if 
for some polynomial p.
of length 2n, then it is possible that the oracle machine M can use z as the new query string to obtain, in one move, the answer 
, which would have taken 2n moves if M were to write down the query string z on the query tape by itself. This problem cannot be avoided by requiring, for instance, that the length 
of the answer relative to the length 
of the query be bounded by a polynomial function, because repeated queries using the previous answers could create large queries in a small number of moves. Note, however, that we have carefully required that the oracle f must, after writing down the answer z, move the tape head of the query tape to the leftmost square of z, and yet M needs to move it to the rightmost square of z to query for f(z). Thus, this problem is avoided by this seemingly arbitrary requirement.Definition 2.22
to denote the class 
and 
to denote the class 
, if 
is a class of sets.
is both reflexive and transitive and, hence, is indeed a reducibility. Furthermore, it is easy to see that it is weaker than 
.Proposition 2.23
Proposition 2.24
Proof
be a complexity class. Recall that a set A is 
-hard for 
if 
for all 
. We say a set is 
-hard to mean that it is 
-hard for class 
.
to be the number of squares the machine M visits in the computation of 
, excluding the input and output tapes. A problem with this definition is that the space complexity of accepting a set A, using itself as the oracle, would require a linear space, because we need to copy the input to the query tape to make the query. This seems too much space necessary to compute the identity operator. When we consider the set-oracle TMs, note that each query is written to the query tape and then, after the query is answered, is erased by the oracle. Thus, the query tape serves a function similar to the output tape, except that this “output” is written to be read by the oracle instead ofthe user, and it seems more reasonable to exclude the query tape from the space measure. To prevent the machine from using the space of query tape “free” for other purposes, we can require that the query tape be a write-only tape, just like the output tape. These observations suggest us to use the alternative approach for the space complexity of oracle TMs in which the query tape is a write-only tape and is not counted in the space measure. It should be warned, however, that this space complexity measure still leads to many unsatisfactory properties. For instance, the polynomial-space Turing reducibility defined by polynomial-space-bounded oracle TMs is not really a reducibility relation because it does not have the transitivity property (see Exercise 2.16). Furthermore, if we extend this notion to more general types of oracle machines such as nondeterministic and alternating oracle TMs (to be introduced in the next chapter), there are even more undesirable properties about polynomial-space-bounded oracle machines. Therefore, we leave this issue open here and refer the interested reader to, for instance, Buss (1986) for more discussions.2.5 NP-Complete Optimization Problems
-complete for NP and then proving that the problems of searching for the optimum solutions are 
-equivalent to the corresponding decision problems. In practice, however, we often do not need the optimum solution. A nearly optimum solution is sufficient for most applications. In general, the NP-hardness of the optimization problem does not necessarily imply the NP-hardness of the approximation to the optimization problem. In this section, we demonstrate that for some NP-complete optimization problems, their approximation versions are also NP-hard and, yet, for some problems, polynomial-time approximation is achievable. These types of results are often more difficult to prove than other NP-completeness results. We only present some easier results and delay the more involved results until Chapter 11.
(or, simply, v(y), if Π is known from the context) to it. The problem Π is to find, for the given input x, a solution y to x such that its value v(y) is maximized (or minimized). For instance, we can fit theproblem MAX-CLIQUE into this framework as follows: an input to the problem is a graph G; a solution to G is a clique C in G; the value v(C) of a solution C is the number of its vertices; and the problem is to find, for a given graph G, a clique of the maximum size.r-APPROX-Π: For a given input x, find a solution y to x such that
, where 
is a solution to 
.r-APPROX-Π: For a given input x, find a solution y to x such that
, where 
is a solution to 
.TRAVELING SALESMAN PROBLEM (TSP): Given a complete graph
with a cost function 
and an integer K > 0,determine whether there is a tour (i.e., a Hamiltonian circuit) of G whose total cost is less than or equal to K.