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.
A to 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.
A?B implies that, but is not the same as, any fast solution to B can be used to solve A quickly.
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.
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
? 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 with respect to the ordering ? of difficulty, changing the base makes no difference at all.