Microsoft PowerPoint – lecture6 [Compatibility Mode]
COMS4236: Introduction to
Computational Complexity
Spring 2018
Mihalis Yannakakis
Lecture 6, 2/1/18
Outline
• Nondeterministic Time to Deterministic Space and Time
• Nondeterministic Space to Deterministic Space
Recall: So far
For all f(n)
TIME(f(n)) Í NTIME(f(n))
SPACE(f(n)) Í NSPACE(f(n))
TIME(2O((f(n)+logn))
Í Í
Í
Nondeterministic Time to
Deterministic Time and Space
• Theorem: If a language LÎNTIME(f(n)), i.e. L is accepted by
a NTM M with time complexity O(f(n)), then it is accepted by
a deterministic TM M’ that uses space O(f(n)) and runs in
time for some constant c.
• Sketch: Assume wlog that M takes ≤f(n) time. Every
configuration of M has at most a constant number d of next
configurations (d depends on M). For an input x, consider
the tree T of configurations of M on input x:
• root=initial configuration
children of a configuration C = set of next configurations
– degree of the tree ≤ d
– height of the tree ≤ f(n)
( )( )f nO c
Nondeterministic Time to Deterministic
• A computation of T corresponds to a sequence of ≤ f(n)
choices of moves, i.e. a sequence of length ≤f(n) over
{1,…,d}
• The TM M’ generates in order every sequence of length ≤
f(n) over {1,…d} in an extra tape, and simulates the NTM M
for this sequence of choices
– If M accepts for a sequence , then M’ also accepts and
halts, else it goes on to generate the next sequence
• If none of the sequences make M accept, then M’ rejects and
halts.
Deterministic TM M’ generates
all the computations of T,
reusing the same space
T
Time Analysis
• The tree T has at most
nodes (configurations)
• In each stage, the TM M’ can generate the next sequence
in time O(f(n)) (similar to incrementing a counter), and
simulate M for this sequence in time O(f(n))
• Total time of M’ is
(take for example c=2d and use the fact that )
2 ( ) ( ) 1 ( )1 ( )f n f n f nd d d d O d
( ) ( )( ( ) ) ( )f n f nO f n d O c
( )( ) 2f nf n
Nondeterministic Time to Deterministic Space
• NTIME(f(n)) Í SPACE(f(n))
• Simulation of NTM M by the DTM M’ uses only O(f(n))
space:
– Need only f(n) space to keep track of the sequence of
choices and increment in each stage
– Simulation for each sequence takes space O(f(n)) (every
computation of M halts in f(n)≥n steps uses at most
O(f(n)) space)
– Note that the same space is erased and reused for every
computation
Relations so far
TIME(f(n)) Í NTIME(f(n))
Í
SPACE(f(n)) Í NSPACE(f(n))
Í
O(f(n)+logn)TIME(2 )
Nondeterministic to Deterministic Space
• NSPACE(f(n)) Í SPACE(f(n)²) for f(n)≥logn
(Savitch’s Theorem)
• Reachability Î SPACE(log²n)
Nondeterministic to Deterministic Space
• For NTM M with space complexity f(n), input x:
Configuration Graph G[M,x], initial node (config) C0
• Assume wlog that unique accepting configuration C*
(TM at the end erases its work tapes and moves heads to left end)
• N=#nodes for some constant c that depends on M
• M accepts x iff C0 can reach C* in G[M,x]
• If there is a path from the initial configuration C0 to the
accepting configuration C* then there is one of length ≤N
• Basic idea: Divide and Conquer the accepting path
( )2cf n
Predicate REACH(C,C’,i)
• Define predicate REACH(C,C’,i):= true iff C can reach C’ in
at most steps.
• M accepts x iff REACH(C0,C*,cf(n))
• Recursive Definition of REACH predicate:
• REACH(C,C’,0) iff C=C’ or CC’ (in one move of M)
• REACH(C,C’,i) for i>0 iff
Z. REACH(C,Z,i-1) REACH(Z,C’,i-1)
Reason: Take Z = midpoint of the path from C to C’
2i
Recursive algorithm REACH
Straightforward recursive algorithm:
REACH(C,C’,i)
if i=0 then if (C=C’ or CC’) then return true else false
else /* i≥1 */
for each configuration Z that uses space ≤f(n) do
{ if REACH(C,Z,i-1) REACH(Z,C’,i-1) then return true}
return false
Main Call: REACH(C0,C*,cf(n))
Analysis
• REACH(C,C’,i) reuses the same space for each of the
recursive calls that it makes for each Z.
• Recursion stack consists of a sequence of records of the
calls that are active (can assume that if a left call
REACH(C,Z,j) returns false then we go on to the next Z).
• Stack: (C0,C*,cf(n)),(C1, C’1,cf(n)-1), (C2, C’2,cf(n)-2), ….
(in each pair, one configuration= one in the previous pair)
• Length of the stack ≤ cf(n)
• Each record takes space O(f(n))
• Total space O(f(n)²)
• Can implement on a Turing Machine
• Use a work tape that contains the stack
A subtle point
• We must be able to generate the configurations Z that use
space ≤ f(n).
• Do we know what f(n) is?
• And can we measure easily a tape of that length?
• Two solutions
• Solution 1 (Without any knowledge of f(n)).
• Try the algorithm with f(n)=1,2,3,….
• For each value i = 1,2,3,…
• if REACH(C0,C*,c·i+logn)=true then accept (and halt)
Else (i.e. REACH(C0,C*,c·i+logn)=false)
for each configuration Z that uses space exactly i,
test REACH(C0,Z,c·i+logn);
If false for all such Z’s (M uses space