Transcript Document

Automata, Grammars and Languages
Discourse 07
Reduction
C SC 473 Automata, Grammars and Languages
Reduction of One Problem to Another
• Often want to solve a new problem P similar to a problem
Q that has already been solved.
• One way of solving P is to transform each instance of P
into an instance of the known problem Q, then solve the Q
instance, and then use it to obtain a solution to the P
instance.
• The solution to P uses the solution to Q as a “subroutine”.
• We often write P  Q for “P is reducible to Q”
2
a
 aa
• Ex: Squaring  Multiplication:
• Ex: Multiplication  Squaring:
a  b  ((a  b)2  a 2  b2 ) / 2
• Ex: DFA Equivalence  DFA Emptiness
L( A)  L( B)  L( A  B)  
C SC 473 Automata, Grammars and Languages
2
Using Reduction to Prove “Difficulty”
• If P  Q and P is known to be “hard to solve”, then Q must
be hard to solve too.
• For example¶, if P  Q and P is undecidable, then Q must
also be undecidable. For if Q is decidable, we can use the
reduction P  Q to construct a decider for P; contradiction.
• Ex: We will show by reduction that the problem
ATM  { M , w | M is a TM and M accepts input w}
is reducible to the problem
HALTTM  { M , w | M is a TM and M halts on input w}
• The undecidability of ATM will imply the undecidability of
HALTTM
_______________________________
¶Here  stands for many-one or mapping reduction denoted 
m . It will
be defined precisely later.
C SC 473 Automata, Grammars and Languages
3
Undecidability via Reductions: Halting
• HALTING PROBLEM
HALTTM  { M , w | M is a TM and M halts on input w}
• ACCEPTANCE (MEMBERSHIP) PROBLEM
ATM  { M , w | M is a TM and M accepts input w}
• Thm 5.1: HALTTM is undecidable.
Pf: We show that ATM  HALTTM , so that if we had a
decider for HALTTM we could build a decider for ATM
This contradicts the undecidability of ATM , and so
HALTTM must be undecidable.
Assume, contrary to what is to be proved, that HALTTMhas
ATMis
a decider R. Following is a visual proof that
reducible to
: TM
HALT
C SC 473 Automata, Grammars and Languages
4
Undecidability via Reductions (cont.)
Consider a “compiler” (algorithm) C that given  M 
constructs a new TM C( M ) as follows:
C( M ) :
acc
acc
M
M, x
U
x

rej
C ( M ) halts on
loop
input x  x  L(M )
Reduction: use this and R to build a decider for
S:
M,w
C
C ( M ), w
ATM
acc
R
rej
M , w  L( S )  C ( M ), w  L( R) 
C ( M ) halts on input w  w  L( M )  L( S )  ATM
So S is a decider for
C SC 473 Automata, Grammars and Languages
ATM .Contradiction  theorem. 
5
Undecidability: Empty Tape Acceptance
• Thm: The EMPTY-TAPE-ACCEPTANCE problem is
undecidable: ETTM  { M | M is a TM and   L(M )}
Pf: We will show that ATM  ETTM . Consider a
“compiler” C that given M,w constructs TM C(M,w ):
C( M , w ) :
M,w
x
U
acc
acc
rej
rej
C( M , w ) accepts the empty tape  w  L(M )
In fact:
C SC 473 Automata, Grammars and Languages
C ( M , w ) accepts   w  L( M )
C ( M , w ) accepts   w  L( M )
6
Empty Tape Acceptance (cont’d)
• Reduction: assume a decider R for ETTM . We
construct a decider from it for ATM .
E:
M,w
C
C( M , w )
acc
R
acc
rej
rej
M , w  L( E )  C ( M , w )  L( R )
   L(C ( M , w ))  w  L( M )
 ATM  L( E )
• E is a decider for ATM . Contradiction. 
C SC 473 Automata, Grammars and Languages
7
Undecidability: Empty Set Acceptance
• Thm: The EMPTY-SET-ACCEPTANCE problem is
undecidable: ETM  { M | M is a TM and L( M )  }
Pf: We will show that ATM  E TM . We reduce the
complement of ATM to this problem. Consider a “compiler”
C that given M,w constructs TM C(M,w ):
C( M , w ) :
M,w
x
U
acc
acc
rej
rej
 * if w  L( M )
L(C ( M , w ))  
 if w  L( M )
C SC 473 Automata, Grammars and Languages
8
Empty Set Acceptance (cont’d)
• Reduction: assume a decider R for ETM . We
construct a decider from it for ATM .
L(C( M , w ))  
E:
M,w
C
C( M , w )
acc
acc
R
rej
rej
L(C( M , w ))  
M , w  L( E )  C ( M , w )  L( R )
 L(C ( M , w ))    w  L( M )
 ATM  L( E )
• E is a decider for ATM . Contradiction  theorem 
C SC 473 Automata, Grammars and Languages
9
Undecidability: Regular Set Acceptance
• Thm 5.3: The REGULAR-SET-ACCEPTANCE problem is
undecidable:
REGULARTM  { M | M is a TM and L(M ) is regular}
Pf: We will show that ATM  REGULARTM . Consider a
“compiler” C that given M,w constructs TM C(M,w ):
C( M , w ) :
(2)
M,w
U
(1)
x
{0 1 | n  0}
decider
n n
acc
acc
rej
acc
rej
 * if w  L( M )
L(C ( M , w ))   n n
{0 1 |n  0} if w  L( M )
C SC 473 Automata, Grammars and Languages
10
Regular Set Acceptance (cont’d)
.
• Reduction: assume a decider R for REGULAR
.
We
TM
construct a decider from it for
. ATM

L
(
C
(
M
,
w
))


E:
M,w
C
C( M , w )
acc
R
acc
rej
rej
L(C( M , w ))  {0n1n}
M , w  L( E )  C ( M , w )  L( R )
 L(C ( M , w ))    w  L( M )  ATM  L( E )
• E is a decider for ATM . Contradiction  theorem 
C SC 473 Automata, Grammars and Languages
11
Mapping Reduction: Motivation
S
x
C
R
Y
N
Y
N
L( S )  m L( R )
• Halting Problem L( S )  ATM L( R)  HALTTM
M , w  L( S )  C ( M ), w  L( R)
• Empty-Tape Acceptance Problem L( E )  ATM L( R)  ETTM
M , w  L( E )  C ( M ), w  L( R)
• Empty-Set Acceptance Problem L( E )  ATM L( R)  ETM
M , w  L( E )  C ( M ), w  L( R)
L( E )  ATM
• Regular-Set Acceptance Problem
L( R)  REGULARTM
M , w  L( E )  C ( M ), w  L( R)
C is an algorithm in each case
C SC 473 Automata, Grammars and Languages
12
TMs can Act as Recognizers or Transducers
• Defn 5.17: A function f :   
is a computable
function† if  a TM transducer M such that on every input
w, M halts with f(w) on its tape. Such a TM is called an
algorithm.
Compare & contrast this definition with:

L


• Defn 3.6: A language
is a decidable
language if  a TM recognizer M such that on every
input w, if w  L it halts with “accept” and if w  L it halts
with “reject” . Such a TM is called a decider.
A recognizer can be viewed as a special case of a transducer that
prints only a 1 or 0


A language can be viewed as a special case L :   {0,1} of a
function that returns a boolean value.
____________________________

†Also called total computable function. “Total” means “defined for
all arguments w”.
C SC 473 Automata, Grammars and Languages
13
Function:Set :: Transducer:Recognizer
f :   
Sets (Languages)
Special case of
Computable† f
 TM transducer M 
• (w) M on w halts & prints M(w)
• (w) M(w) = f(w)
M is called an algorithm
L  
Decidable L
 TM recognizer M 
• (w) M on w halts & prints 0,1
• (w) M(w) = 1  w L
M is called a decider ‡
Special case of
Partial† Computable f
 TM transducer M 
• (w) M on w halts  f(w) defined
• (w) M(w) = f(w)
M is called a procedure
Recognizable L
 TM recognizer M 
• (w) M on w halts  w L
• (w) M(w) = 1  w L
M is called a recognizer
Special case of
Functions
Special case of
C SC 473 Automata, Grammars and Languages
14
Mapping Reduction: Definition
L( M A )  A  m L ( M B )  B
MA
x
f
MB
Y
N
• All have the same pattern


Y
N
A m B
x  A  f ( x)  B
f must be a computable function
The “compiler” must be an algorithm
• Defn 5.20: Language A is mapping reducible to
language B iff  a computable function f :   
such that (x) x  A  f ( x)  B. Function f is called
the reduction of A to B .
C SC 473 Automata, Grammars and Languages
15
Mapping Reduction: Definition (cont’d)
A  L( M A )
MA
B  L( M B )
f
x
MB
Y
N
Y
N
A m B
• Picture: f :   


A

f
B

x A 
f ( x)  B
equivalent to
x A 


f ( x)  B
A m B
x  A  f ( x)  B  x  A  f ( x)  B
f
C SC 473 Automata, Grammars and Languages
16
Reduction (cont.)
• Thms 5.22, 5.23,5.28, 5.29: Let




B
A
B
A
A  m B . Then
decidable  A decidable
hardness
undecidable  B undecidable
recognizable  A recognizable
non-recognizable  B non-recognizable
easiness
B
A
If you want to show a problem P is easier than
problem Q then reduce P to Q
P:
? Q

If you want to show a problem P is harder than
problem Q then reduce Q to P
Q:
? P

C SC 473 Automata, Grammars and Languages
17
Reductions
• Thm:
A m B  A m B
• Ex: ATM  m ETM  ATM  m ETM
• Reduction: major method for showing unsolvability or nonrecognizability:

Goal: to show LTEST is not recognizable [not decidable]

Known: LBAD
is not recognizable [not decidable]

Strategy: reduce LBAD to LTEST ( LBAD  m LTEST )

Method: build computable “translator” f to accept LBAD
assuming we have a recognizer [decider] for LTEST
LBAD recog.
w
yes
f
C SC 473 Automata, Grammars and Languages
LTEST recog.
18
Undecidable via Reductions
• Thm: The NONEMPTY-SET-ACCEPTANCE problem is TMrecognizable but not decidable: NETM  { M | L( M )  }
ETM m NETM since
w  ETM  w  (0  1)  NETM .
So NETM cannot be
Pf: It is easy to see that
decidable.
An acceptor for NETM is the following nondeterministic TM
M
N:
encode
M,w
U
yes
yes
guess w
M  L( N )  (w) w  L(M )  L(M )    M  NETM
C SC 473 Automata, Grammars and Languages
19
Non-Recognizable via Reductions
• Thm: The EQUIVALENCE problem is not recognizable:
EQTM  { M1 , M 2 | M1 , M 2 are TMs  L(M1 )  L( M 2 )}
Pf: We show that EQTM is not recognizable by showing
that ATM m EQTM (which means that ATM  m EQTM ).
C
The reducing function  M , w  
 M1 , M 2 generates a
pair of TMs with the following behaviors:
M1
rej
x
L( M 1 )  
M2
x
acc
M,w
U
w  L ( M )  L( M 2 )  
w  L( M )  L( M 2 )  
w  L( M )  L( M 2 )  L( M 1 )
C SC 473 Automata, Grammars and Languages
w  L( M )  L( M 2 )  L( M 1 )
20
Non-recognizable via m (cont’d)
• Reduction: assume a decider R for EQ TM. .
We construct a decider from it for ATM .
L(M1 )  L(M 2 )
S:
M,w
C
M1 , M 2
acc
R
M , w  L( S )  M 1 , M 2  L( R )
 L( M 1 )  L( M 2 )  w  L( M )
acc
rej
rej
L( M 1 )  L( M 2 )
 ATM  L( S )
• S is a decider for ATM . So ATM m EQTM.
This
implies that ATM m EQTM , and so EQTM cannot be
recognizable 
C SC 473 Automata, Grammars and Languages
21
Non-Recognizable via Reductions (cont’d)
• Exercise: The FINITE-SET-ACCEPTANCE problem is not
TM-recognizable: FTM  { M | L(M ) is finite}
Proof: Show that ATM  m FTM
• Exercise: The INFINITE-SET-ACCEPTANCE problem is
not TM-recognizable: I TM  { M | L(M ) is infinite}
Proof: Show that ATM  m I TM
C SC 473 Automata, Grammars and Languages
22
Equivalence ( m ) and Completeness
• Definition: Let C be a class of sets. A set A is mapping
reduction complete (  m -complete ) in C iff

AC

 B C

B m A
Remark: “A is complete” says A is a “hardest problem in C”
A is mapping equivalent to B ( A  m B) iff
A m B & B m A
• Fact: all complete sets in C are mapping equivalent
ATM m HALTTM m NETM
• Exercise:
ATM m HALT TM m ETM
C SC 473 Automata, Grammars and Languages
23
Completeness
• Theorem: ATM is complete in the class TM of Turingrecognizable sets.
Proof: ATM is accepted by U, so is in TM.
To show completeness, let B be any Turing-recognizable
set in TM. Then  a TM M B such that B  L( M B ) .
Define the computable function
Then
c( x)  M B , x
x  B  x  L(M B )  M B , x  ATM  c( x)  ATM
 B m ATM
Since B was chosen arbitrarily in TM the result follows 
• Exercise: Show the Halting Prob. HALTTM is complete in
TM
C SC 473 Automata, Grammars and Languages
24