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

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: xy is 1 (resp. 0) iff both x=y=1 (resp. x=0 or y=0)
OR: xy 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. xyzw = (xy)(zw)

Boolean Formula: Expression built from variables and ,,
Example: ((xyz) (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: ((xyz) (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.