Microsoft PowerPoint – lecture10 [Compatibility Mode]
COMS4236: Introduction to
Computational Complexity
Spring 2018
Mihalis Yannakakis
Lecture 10, 2/15/18
Outline
• Reachability is NL-complete
• Boolean Circuits and formulas
• Circuit Value problem
• P-completeness
Example
• Undirected Reachability ≤log Directed Reachability
Given undirected graph G, nodes s,t , replace every
undirected edge by two opposite directed edges
Directed graph D, same s, t
– G has a path from s to t iff D has a path from s to t
– Can perform reduction in log space
Reachability is NL-complete (under log reductions)
• Corollary: NL=L Reachability ÎL
• Must show: For every language L in NL there is a
logspace reduction from L to Reachability.
• Take a language L in NL , let M be NTM that decides L
in space logn. Must construct a O(logn)-space
(deterministic) TM M’ that maps every string x over the
input alphabet of L to an instance (graph G, nodes s,t)
such that xÎL iff s can reach t in G
• G = configuration graph of M on input x
• s = initial configuration
• t = accepting configuration (assume wlog unique)
• Remains to show how to construct G in log space.
Construction of Configuration Graph
• Can generate graph for example as a list of nodes,
followed by a list of edges
• Nodes: Enumerate systematically all configurations of M
(remember, not including the input) that use space ≤logn
• Edges: Generate each logn-space configuration C of M,
and for each possible move of M from C, generate the
next configuration C’ and output edge (C,C’)
• Output s= initial configuration, t=accepting configuration
• Only need to keep track of the current configuration C
being considered, and generate the next config. C’
• O(logn) space
Boolean Algebra and Boolean Formulas
Boolean values: 1,0 (true, false)
Boolean variables: Variables that take on Boolean values
Operations (Gates)
NOT: x is 1 (resp. 0) iff x=0 (resp. x=1)
AND: xy is 1 (resp. 0) iff both x=y=1 (resp. x=0 or y=0)
OR: xy is 1 (resp. 0) iff x=1 or y=1 (resp. x=y=0)
, are associative and commutative
Can write , of more than 2 variables
eg. xyzw = (xy)(zw)
Boolean Formula: Expression built from variables and ,,
Example: ((xyz) (w(x))) (y (z))
Boolean Circuit
Directed Acyclic Graph with two kinds of nodes: inputs and
gates
• indegree 0 nodes = inputs: labeled with Boolean variables
or Boolean constants (0,1)
• other nodes gates labeled with operations
NOT gate: 1 incoming edge; – gate negates its input
AND, OR gates: 2 or more incoming edges
– computes , of its inputs
Fan-in: Number of incoming edges of gates
• outdegree 0 nodes = outputs
DAG Topological ordering of the nodes.
Usually assume nodes are ordered so arcs go from low to
high: first inputs, then gates, then outputs
Monotone Circuit: If no NOT gates (only AND, OR)
Example
x y z Inputs
Output
Gates
Assignment of values to Inputs
Assignment to all the Gates
x y z
0 10
0
0
1 1
11
0
0
C(001) = 0
Inputs
Output
Gates
Boolean Formulas vs. Circuits
• Boolean formulas can be seen as special case of circuits:
1 output, and all other nodes have outdegree 1 (only 1
successor), i.e. DAG is a tree
Example: ((xyz) (w(x))) (y (z))
x x
y
y
z
z w
Boolean Circuits vs. Functions
• If n inputs, m outputs, Boolean circuit computes a function
• For every Boolean function f there is a Boolean circuit that
computes it:
• Suppose wlog one output (m=1)
• List all input assignments s.t f()=1
• Each assignment monomial that is of variables or
their negations
For example if =110 (x1 =1, x2=1, x3=0) then x1 x2 (x3)
• Boolean Formula = OR of monomials for all s.t f()=1
= Disjunctive Normal Form of a Boolean Function
Boolean circuit – In general, size is exponential in n: O(n2ⁿ)
• If many outputs, then union of the circuits.
:{0,1} {0,1}n mf
Boolean circuits vs. Turing machines
• Turing machines, RAM are uniform models of computation:
one machine (program) for all inputs of all sizes
• Boolean circuits are a nonuniform model: one separate circuit
Cn for each input size n
• Problem Family of circuits {Cn | all n }
• Parameters (Resources) for Boolean circuits
• Size : # gates and wires
• Depth : length of longest path from input to output
• Relationships:
• Size of circuits ~ Time of TMs (up to polynomial): show next
• Depth (for fan-in 2 circuits) ~ Parallel Time ~ Space (not now)
A P-complete problem: Circuit Value Problem
• Input: Boolean combinational circuit C (composed of
AND,OR, NOT gates) with several inputs, one output, an
assignment of Boolean values to the inputs
• (Alternatively and equivalently: Input = Boolean circuit with
no variables; all inputs 0 or 1.)
• Output: Yes, if C outputs 1 for the given input assignment,
No otherwise
Theorem: The Circuit Value problem is P-complete under log-
space reductions
Corollary: P=L (resp. P=NL) iff Circuit Value is in L (resp. in
NL)
Circuit Value is in P
• Given circuit C, input assignment ,
• Compute topological order of the nodes (if circuit
is not given in this order), and
• evaluate the gates in topological order
Circuit Value is P-hard (under logspace reductions)
• Must show, for every language L in P
L ≤log Circuit Value
• To prove this, we must design log-space reduction that
constructs from a string x over the alphabet of L a circuit
Dx and input assignment x such that for all strings x
xÎL Dx(x ) = 1
• Fix a polynomial time 1-tape TM M for L (exists by 1-tape
simulation theorem). Could do the reduction using a
multitape TM for L, but more convenient with 1 tape.
– M runs in time ≤ nc =p for all n uses space ≤ p
• Assume wlog that when M enters the yes or no state, it
cleans its tape, moves the head to cell 1 and stays there.
• Will construct circuit Dn that depends only on length n of x
(not x itself); input assignment x depends on x
Tableau T of the computation
s 0 1 0 0 1 0
0q 1 0 0 1 1
1 1p 0 0 1 2
1 1 0r 0 1 3
………………………………………………..
………………………………………………..
yes p
tape cells
0 1 2 3 4 5 . . . . p
time
T[i,j] = symbol in cell i at time j, if tape head not there
(symbol,state) in cell i at time j, if head there
Tableau of Computation
• Row 0 = initial configuration
• Row i depends on row i-1
• T[i,j] depends only on 3 cells: T[i-1,j-1], T[i-1,j], T[i-1,j+1]
i-1,j-1 i-1,j i-1,j+1
i,j
• Extended Tape alphabet: K let k=||
• Encode in binary, for example map each i Îto a k-tuple
with 1 in the i-th position and 0 in other positions
• Each T[i,j] represented by k Boolean values B[i,j,1], …B[i,j,k]
• Tableau T represented by array B of Boolean values
Boolean Tableau of Computation
• B[i,j,1],…,B[i,j,k] depend on 3k values in the previous row
B[i-1,j-1,1],…,B[i-1,j+1,k]
• There is Boolean Circuit C that computes them.
i-1,j-1 i-1,j i-1,j+1
i,j
C
B[i,j,1] . . . B[i,j,k]
B[i-1,j-1,1] B[i-1,j+1,k]. . . . .
• Circuit C has 3k inputs, k outputs and g gates,
where g is a function of k
• For the first and last column of the tableau, only 2
cells in previous row matter
2 3( 3 2 )kg k
Circuit Dn for Tableau of Computation
• One copy C[i,j] of C for each [i,j], i=1,…p; j=0,…p
• Identify inputs of C[i,j], i>1 with the output gates of the
circuits C[i-1,j-1], C[i-1,j], C[i-1,j+1] from the previous row
B[i-1,0,1]
B[i,0,1]
B[i-1,p,k]
B[i,p,k]
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅
C C C C C
• Inputs: B[0,..] for row 0.
• Output: Bit in row p that states “cell 0 is yes” .
• Input assignment x = bits 0,1 according to input x
• Dn(x) =1 M accepts x, i.e. xÎL
Log space construction of Dn, x
• For a given n=|x|, Circuit Dn depends only on n, not on the
input x.
• We can generate Dn in log space by listing the gates and
the edges of each copy C[i,j] of C in order from row i=1,
j=0 to p, to the last row p. All we need is two counters to
keep track of i and j (the third parameter k is a constant).
Nodes (and their edges) listed in topological order.
• The input assignment x generated easily from input x.