
142
11 Reduction in ptime
We now use Turing machines to formalise the technique we saw in ?8.6 of reducing one problem to another in ptime. This ptime reduction gives fast nondeterministic solutions to new yes/no problems from known fast nondeterministic solutions to old ones. We'll study its properties.
11.1 DEFINITION OF PTIME REDUCTION
Let A, B be any two yes/no problems (not necessarily in NP or even
solvable by a Turing machine).
1. Let X be a deterministic1 Turing machine. We say that X reduces A to B
if:
? for every yesinstance w of A, fX(w) is defined and is a yesinstance
of B
? for every noinstance w of A, fX(w) is defined and is a noinstance
of B.
2. We say that A reduces to B in polynomial time (or ptime) if there exists a
deterministic Turing machine X running in ptime that reduces A to B.
3. We write A ? B if A reduces to B in polynomial time.
4. We write A ~ B if A ? B and B ? A.
If A?B then as in ?8.6 we can use a fast solution to B to solve A quickly, by first reducing the instance of A to an instance of B of the same ?parity? (yes or no), and then applying the fast solution to B.
TM to
reduce
A to B
TM to
solve B
TM that solves A
11.1 If A?B, and we are given a solution to B, then we can solve A
1 We want X to be deterministic because it should be ?genuinely fast?, and have an output.
143
11.1.1. Warning
A?B implies that, but is not the same as, any fast solution to B can be used to
solve A quickly.
11.2 EXAMPLES
11.2.1 Example
By ?8.6, HCP reduces to TSP, and the reduction can easily done by a
deterministic Turing machine running in ptime. So HCP ? TSP.
11.2.1.1 Warning
Don't try to reduce HCP to TSP in ptime as follows: given an instance G
of HCP,
? If G is a yesinstance of HCP, output 1
1
1 d=3
? If G is a noinstance of HCP, output 3
9 5 d=1
This involves determining whether G is a yes or a noinstance. This is hard to do. There is no known ptime way to do it, so this reduction is (probably) not ptime.
A machine reducing a problem A to another, B, need not be able to solve
A; and its design does not necessarily take account of whether it is given a
yes or a noinstance of A. It may be very hard to solve A, and yet quite easy
to reduce A to B, by making simple changes to the instances in a way that
preserves their yes?no parity.
For an apparent exception, see ?11.5.2 below.
11.2.2 Example: change of base
Let a,b?2. We can design a deterministic Turing machine Xa,b running in
ptime, such that for any number n, if w represents n in base a then fXa,b(w)
represents n in base b. Change of base of arithmetic can be done in
polynomial time.
For any number a?2, let Ca be the yes/no problem ?is w the representation
in base a of a prime number??. Then for any a, b ? 2, Xa,b reduces Ca to Cb.
(Exercise: check this.) So Ca?Cb (and by symmetry, Cb?Ca) for any a, b?2.
So Ca~Cb.
So with respect to the ordering ? of difficulty, changing the base makes no
difference at all.