Problem Solving in Automata, Languages, and Complexity

5.4 Reducibility 247

Proof. For part (a), the identity function is a reduction function for A Lrn A
for all A C C*.
For pa; (b), assume that A & B by the reduction function f and B srn C
by the reduction function g. Then, the function h(x) = g(f(x)) is a reduction
function for A Frn C. q

Example 5.25 Assume that both A and B are nonempty proper subsets of
c*.
(a) Show that if A is recursive then A Lrn B.
(b) Show that if the set differences A \ B and B \ A of sets A and B are
both recursive, then A & B.

Proof. (a) Let x0 be a fixed string in B and xl a fixed string in B. Define

f(s) = {

x1 if x E A,

x0 ifxeA.

Then, it is clear that x E A if and only if f(x) E B. In addition, the predicate

[x E A] is recursive and so f is recursive. Thus, f is a reduction function for

A Lrn B.

(b) Similarly to part (a), we choose two strings x0 E B and xl E B and

define

x1 ifxEA\B,

d x > = x0 ifxe B\A,

X otherwise.

Then, f is recursive since both A \ B and B \ A are recursive. In addition,

if x E A then either g(x) = x1, or [g(x) = x and x e A \ B]; in either case,

we have g(x) E B. Similarly, if x $ A then either g(x) = x0 or [g(x) = x and

x 4 B \ A]; in either case, g(x) 4 B. It follows that g is a reduction function

for A srn B.^0

Proposition 5.26 Assume that A Lrn B.

(a) If B is recurisve then A is recursive.

(b) If B is r.e. then A is r.e.

Proof. Suppose A & - B by the reduction function f. Then, XA(x) =

XB (f (2)) and SA (x) = sg (f (2)). Since f is recursive, it follows that XA

is recursive if XB is recursive, and that SA is partial recursive if sg is partial

recursive. Cl

The above theorem allows us to prove a set B to be nonrecursive or non-
r.e. by reducing a set A that is already proven to be nonrecursive or non-r.e. to
set B. For instance, in Corollary 5.20, we showed that set li’o = {(y, x) 1 x E
WY} is not recursive by reducing set li’ = {x ( x E VI&} to it. In that case,
the reduction function is very simple: f(x) = (x, x). The following is another
example.