程序代写代做代考 algorithm Microsoft PowerPoint – lecture7 [Compatibility Mode]

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)²)