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

Microsoft PowerPoint – lecture24 [Compatibility Mode]

COMS4236: Introduction to
Computational Complexity

Spring 2018

Mihalis Yannakakis

Lecture 24, 4/12/18

Outline
• PSPACE-complete problems

• Games
• Geography Game

• Paths in Succinct Graphs
• LBA problem
• Reachable Deadlock problem

• Regular Expression Equivalence and Minimization
• Nondeterministic Finite Automata

Geography Game
• Ordinary game: Two players, I and II, alternate naming

cities. Rules: Next city must (i) start with last letter of the
last city, and (ii) differ from all previous cities. A player
wins if opponent cannot name a next city.

• Generalization: Input: Graph G whose nodes play the role
of cities and arcs specify rule (i), i.e. which “city” can follow
which city. Game starts at a specified node s, with a
specified player, say I, going first.

• Question: Does Player I have a winning strategy?

• Generalized Geography Game is PSPACE-complete

Geography Î PSPACE
• Recursive algorithm Win(G,s) to determine if the player

that goes first wins the game on graph G starting at s
• if there is no edge (s,v) in G then return No else

for every edge (s,v) of G, call Win recursively on (G-{s},v)
and if one of these calls answers No, then return Yes,

else return No

• Depth of recursion = #rounds = n =# nodes of graph G
• Recursion stack = sequence of nodes deleted from the

graph
 polynomial space

Geography is PSPACE-complete

• Reduction from Q3SAT. Assume wlog that quantifiers
alternate, starting and ending with :

• Input F = y1 y2 y3… ym y1,y2,…,ym)
where = C1  C2  …  Ck

• Player I corresponds to Existential Player E, Player II to
Universal player U

• We will construct a graph G with initial node s, such that
Player I has a winning strategy iff F is true

• Graph has (1) a variable section, where players choose
a truth assignment for the variables, and (2) a clause
section to test the assignment

The variable section

s

y1 y2 y3 ym
1 1 11

0 000

Odd diamonds: Player I (E) chooses the path

Even diamonds: Player II (U) chooses the path

• In initial path through the variable section, the players
alternate choosing a truth assignment, Player I for the
existential variables, Player II for the universal variables

The Game Graph
y1 y2 y3 ym

C1 C2
Ck

1 1 2 3C y y y  
If a clause is not satisfied, then Player II
can choose that clause and win

s
1 1 11

0 0
00

Paths in Succinct Graphs
• Acceptance of an input x by a PSPACE machine M 
 path in configuration graph G[M,x] from initial
configuration C0 to accepting configuration C*

• G[M,x] an exponential size graph, given implicitly via x

Linear Bounded Automaton (LBA)
• Linear Bounded Automaton (LBA): A one-tape TM that

does not use any space besides the input (assume input
has left and right endmarker, so head stays within bounds).

• Usually LBA are allowed to be nondeterministic, but the
following PSPACE-completeness results apply even to
deterministic LBA.

LBA Problem (in-place acceptance)

• There is a (fixed) deterministic LBA A whose acceptance
problem is PSPACE complete.

• Input: String x
• Question: Does A accept x?

• Note: A is not part of the input

• Clearly in PSPACE.

LBA Problem is PSPACE-complete

• QSAT is in PSPACE, i.e. there is a TM M that decides it in
space p(n).

• By 1-tape simulation theorem, we can assume that M has 1
tape.

• Can pad input to length p(n) so that M does not use any
extra space.

• That is, pad(QSAT,p(n)) is also obviously PSPACE-
complete, and is decided in-place (without extra space) by
a deterministic LBA.

• Let A be this LBA.

Communicating/Distributed Processes
• Many problems involving systems of processes that

communicate with each other or that operate in parallel
sharing resources, are typically PSPACE-complete.

• Input specifies the set of processes, e.g. in terms of states
and transitions, and communication / synchronization
between the processes.

• Global operation of the set of processes described
implicitly by the input: exponential-size global transition
graph G whose nodes specify the state of each process
and whose edges specify the transitions.

• Questions about the global operation of the system
concern this implicitly defined exponential global graph.

• Example- Deadlock problem: Can the set of processes
ever deadlock?

Reachable Deadlock Problem
• Input: A set of communicating processes P1, …, Pk, initial

state si for each process Pi
• Each process Pi is given as a finite directed multigraph

(nodes=states, edges=transitions) with labeled edges.
Assume that each label appears in two processes; it
specifies a synchronization event between the two
processes (eg. transmission and reception of a message).

• Global transition graph:
• Nodes = {(q1,..,qk)| qi node of Pi for all i }
• Edges: (q1,..,qk)(r1,..,rk) if they are equal except for two

coordinates i,j and edges (qi,ri) of Pi and (qj,rj) of Pj have
the same label

• Question: Can the initial state (s1,..,sk) of the global
transition graph reach a deadlock state (one that has no
outgoing edge)?

Reachable Deadlock is PSPACE-complete

• In PSPACE: A nondeterministic TM can guess the path in
the global graph G from the initial state s= (s1,..,sk) to a
deadlock state one node at a time. We need only to
remember the current node: polynomial space.

Since NPSPACE=PSPACE  in PSPACE

Reachable Deadlock is PSPACE-complete
• PSPACE-hard. Reduction from the LBA problem.
• Let A be a (fixed) deterministic LBA A whose acceptance

problem is PSPACE complete.
• Input: String x
• Question: Does A accept x?

• Given input x of length n to the LBA A (including the
endmarkers) , we have n processes Pi, one for each tape
cell.

• States of each process = extended tape alphabet  
where =tape alphabet, K=set of states of A

• Initial states: correspond to initial configuration

Reachable Deadlock ctd.
• Each process Pi communicates with the one(s) next to it:

Pi-1 and Pi+1
• Suppose A has a transition (q,X)(p,Y,L)
• Then for each i=2,…,n, process Pi has a transition (q,X)Y

and Pi-1 has for each ZÎ transitions Z(p,Z), all labeled
l(q,X,i).

• Similarly, for right-moving transitions of A
• If q is the rejecting state, then for each i,j and symbols X,Z

processes Pi, Pj have transitions (q,X)  (q,X) and ZZ
labeled l(q,X,i,j).

Reachable Deadlock ctd.
• Reachable global states from initial state correspond to

reachable configurations of A on input x.

• A accepts x  path in G to accepting state, which has no
outgoing edge  deadlock

• A rejects x  path in G leads to rejecting state, which has
self-loops  no deadlock

Minimization and Equivalence of
Nondeterministic Finite Automata

• Equivalence Problem
• Input: Two NFA N1, N2
• Question: Are they equivalent? (i.e. L(N1) = L(N2) ?)

• Minimization Problem
• Input: A NFA N
• Output: An equivalent NFA N’ with minimum # states

• Note: For deterministic FA these problems are solvable
efficiently, in O(nlogn) time.

NFA Minimization and Equivalence

• NFA Equivalence and Minimization are PSPACE-
complete

• Equivalence is PSPACE-complete even when one of the
automata is the trivial FA that accepts *, i.e. it is
PSPACE complete to determine whether a given NFA
accepts all strings

• * is as simple a language as it gets.
• Determining if L(N)=  (the empty language) is a

reachability problem (easy).

Regular Expression Minimization and
Equivalence

• Equivalence Problem
• Input: Two regular expressions R1, R2 using the standard

operators +(union), ⋅ (concatenation), * (Kleene star/closure)

• Question: Are they equivalent? (i.e. L(R1) = L(R2) ?)

• Minimization Problem
• Input: A regular expression R
• Output: A regular expression R’ of minimum length that is

equivalent to R

• Two regular expressions may be inequivalent, but the
smallest counterexample string may have exponential
length in the size of the expressions!

Regular Expression Minimization and
Equivalence

• Regular Expression Equivalence and Minimization are
PSPACE-complete

• Equivalence is PSPACE-complete even when one of the
expressions is *, i.e. it is PSPACE complete to determine
whether a given regular expression denotes the set of all
strings

Leave a Reply

Your email address will not be published. Required fields are marked *