page 1  (11 pages) 2

142

11 Reduction in p-time

We now use Turing machines to formalise the technique we saw in ?8.6 of reducing one problem to another in p-time. This p-time reduction gives fast non-deterministic solutions to new yes/no problems from known fast nondeterministic solutions to old ones. We'll study its properties.

11.1 DEFINITION OF P-TIME 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 yes-instance w of A, fX(w) is defined and is a yesinstance of B
? for every no-instance w of A, fX(w) is defined and is a no-instance of B.
2. We say that A reduces to B in polynomial time (or p-time) if there exists a deterministic Turing machine X running in p-time 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 p-time. So HCP ? TSP.

11.2.1.1 Warning
Don't try to reduce HCP to TSP in p-time as follows: given an instance G of HCP,

? If G is a yes-instance of HCP, output 1

1
1 d=3

? If G is a no-instance of HCP, output 3
9 5 d=1

This involves determining whether G is a yes- or a no-instance. This is hard to do. There is no known p-time way to do it, so this reduction is (probably) not p-time.

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 no-instance 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 p-time, 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.