Microsoft PowerPoint – lecture7 [Compatibility Mode]
COMS4236: Introduction to
Computational Complexity
Spring 2018
Mihalis Yannakakis
Lecture 7, 2/6/18
Outline
• Complements of Nondeterministic Classes
• Nondeterministic space classes closed under
complement (Immerman-Selepscenyi Theorem)
Relations so far
TIME(f(n)) Í NTIME(f(n))
O(f(n)+logn)TIME(2 )
Í
SPACE(f(n))
Í
NSPACE(f(n)) Í
Í
SPACE(f(n)²)
Complements of Problems
• Complement of a language L Í A* is
• Complement of a decision problem: switch Yes and No
• For example, complement of Reachability is
Unreachability: {(G,s,t) | there is no path from s to t}
• When we encode problems in an alphabet, there are
strings that are not in the right format (eg. not the code of
a graph) – Usually we ignore these; for example can
assume that they are mapped to a default instance.
• Definition of acceptance for Nondeterministic machines
is not symmetric with respect to Yes/No answers.
L A L
Complements of Nondeterministic Classes
• Deterministic classes (eg. TIME(f(n)), SPACE(f(n)), are
closed under complement by the definition of acceptance
• L Î Class
• Nondeterministic Classes?
• Complements of nondeterministic classes
Notation:
L Class
coNSPACE(f(n)) { L | L NSPACE(f(n)) }
coNTIME(f(n)) { L | L NTIME(f(n)) }
coClass { L | L Class }
NSPACE(f(n))=coNSPACE(f(n)) for proper f(n)≥logn
(Immerman-Selepscenyi Theorem)
• Recall “proper” function: simple technical condition (satisfied
by common functions) that allows us to easily measure
length f(n) on the tape so that we can enumerate the
configurations that use space f(n)
• In particular: Reachability Î coNL =coNSPACE(logn)
i.e. Unreachability Î NL = NSPACE(logn)
• NL = coNL
NSPACE(f(n))=coNSPACE(f(n)) for proper f(n)≥logn
(Immerman-Selepscenyi Theorem)
• Given NTM M, input x
• Configuration Graph G[M,x]
• M does not accept x iff the initial configuration C0 cannot
reach an accepting configuration in G[M,x]
• Want to show that this Unreachability problem is in
NSPACE(f(n))
• Nondeterministic algorithm for Unreachability
• Phase 1. Compute the number r of reachable nodes from
initial node (configuration)
• Phase 2. Given r, test if one of the reachable nodes is
accepting
Phase 2
• Given r=#reachable configurations, test nondeterministically
if any reachable configuration is accepting
• i =0
for each node C (configuration using space ≤f(n)) do
{ Guess whether C is reachable.
If yes, then guess node by node a path (computation)
from the initial node C0 to C;
if successful then { if C is accepting then reject and halt
else i++ }
}
if i=r then accept
Space complexity: Need to record only r, i, C and current node
in the guessed computation: O(f(n))
Proof of Correctness for Phase 2
• If r = # reachable nodes, then Phase 2 accepts iff initial
node (configuration) cannot reach an accepting node
• Proof:
• The only way for Phase 2 to accept is if i=r there are r
nodes C for which it guessed successfully a computation
from C0 to C and none of them was accepting they are
exactly the r reachable nodes and they aren’t accepting
input x is not accepted by NTM M
• Conversely, if input x is not accepted by M, then all r
reachable configurations are not accepting. Phase 2 can
guess successfully a computation for each of them, and
then will accept x
Phase 1: Counting # reachable nodes
• Let r(i) = # reachable nodes in ≤ i steps for i=0,1,2,…
• r(0) = 1. We will compute r(i) from r(i-1) for i>0.
• Initialize: p =0; p’=1; i=0; /*p will hold r(i-1), p’ will compute r(i)*/
• Repeat
{ i++; p =p’; p’=1; /*next i; set p=r(i-1), p’ includes C0 so far*/
for each node (configuration) C¹C0 do /* is C i-reachable? */
{ d=0 /*d counts (i-1)-reachable nodes that we tried */
for each node C’ /* is C’ ( i-1)-reachable and C’C ?*/
{ guess a path of length ≤ i-1 from C0 to C’;
if successful then { d++; if C’C then p’++ and break out
of the loop and go on to next C }
}
if d¹p then reject and halt else continue to next C
}
}
Until p =p’
r = p
Analysis of Phase 1 – space complexity
• Need to record:
• p, p’, i, d,
• nodes (configurations) C, C’
• the length and current node in the guessed path from C0
to C’.
• Total O(f(n))
Analysis of Phase 1 -correctness
• Show:
• 1. There is a computation of Phase 1 that does not reject
and halts with output r = #reachable nodes.
• 2. Every computation of Phase 1 halts and if it does not
reject, then it outputs the same number, r=#reachable
nodes.
Analysis of Phase 1 –correctness 1
• Correctness: 1. There is a computation of Phase 1 that does
not reject and halts with output r = #reachable nodes.
• Can show inductively that if at the start of i-th iteration
p=r(i-1), then there is a computation (set of guesses) such
that at the end of the iteration p’=r(i)
Proof: In each iteration, for each C, and for each C’, if C’ is
(i-1)-reachable then we can guess the path of length ≤i-1
if C is i-reachable then we will count it at the end of the
iteration p’=r(i)
• At the end, if r(i-1)=r(i) then no more reachable nodes
• Number of iterations bounded by #nodes The
computation halts with correct #reachable nodes
Analysis of Phase 1 ctd
• Correctness: 2. Every computation of Phase 1 halts and
if it does not reject, then it outputs r=#reachable nodes.
• The only guessing is in the C’ loop and the guessed path
has bounded length. If C’ is (i-1)-reachable but guessed
wrong path then we’ll discover d¹p and halt and reject.
• If at the start of i-th iteration p=r(i-1), and iteration does
not reject, then for each C, it successfully found all (i-1)-
reachable nodes C’ at the end p’=r(i)
• If r(i-1)=r(i) then no more reachable nodes
• Number of iterations bounded by #nodes If Phase 1
does not reject it halts with correct #reachable nodes
Summary
TIME(f(n)) Í NTIME(f(n))
O(f(n)+logn)TIME(2 )
Í
SPACE(f(n))
Í
NSPACE(f(n))=coNSPACE(f(n)) Í
Í
SPACE(f(n)²)