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 ZZ
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