Microsoft PowerPoint – lecture19 [Compatibility Mode]
COMS4236: Introduction to
Computational Complexity
Spring 2018
Mihalis Yannakakis
Lecture 19, 3/27/18
Outline
• Circuit Complexity
• Uniform Circuit Complexity
• P vs. Uniform Poly-size circuits
• P/poly
• BPP P/poly
Boolean Circuits and Languages
• Circuit Cn with n inputs x1,…,xn, 1 output, gates NOT, OR,
AND with fan-in 2. Two parameters of interest:
• Size of circuit = # gates
• Depth of circuit = maximum # gates in an input-output path
• C accepts the set of binary strings x=(x1,…,xn) such that
Cn(x)=1
• If is a language then for each length n, we need a
separate circuit Cn to accept the subset of L of strings of
length n (usually denoted as Ln)
• Family of circuits C=(C1, C2,…) where Cn has n inputs,
accepts the language L if for every n and every string x of
length n, Cn(x)=1 xÎL
{0,1}L
Circuit Complexity
• Size complexity of circuit family C=(C1,C2,…) :
s(n)=size(Cn)
• Depth complexity of circuit family C=(C1,C2,…) :
d(n)=depth(Cn)
• Circuit size complexity of a language L over {0,1} =
minimum size complexity of a circuit family that accepts L
(i.e. for every n, pick a circuit Cn of minimum size that
accepts the strings of L of length n).
• Circuit depth complexity of a language L over {0,1} =
minimum depth complexity of a circuit family that accepts L
Circuit complexity and uniformity
• There are undecidable languages that have linear circuit
(size) complexity
• Proof: Take undecidable language L over {0,1}.
Corresponding unary language unary(L) over {1} is also
undecidable. Every unary language has a trivial circuit
family: Cn outputs 1 (resp. 0) iff 1ⁿ ÎL (resp. 1ⁿ L).
• Problem: We can pick a different circuit for every n, but
definition of circuit complexity does not reflect the
difficulty of finding the circuit for each n
• Uniform circuit family: There is a log-space Turing
machine which on input 1ⁿ outputs Cn.
• Uniform circuit size/depth complexity of a language
P vs. Polynomial Circuits
• A language L over {0,1} has uniformly polynomial size
circuits iff LÎP.
• Proof: 1. Suppose LÎP. As in the proof that the Circuit-Value
Problem is P-complete, for each n we can construct a
polynomial size circuit Cn such that for every binary string x
of length n, Cn(x)=1 xÎL. The construction is done by a
log-space TM
• 2. Suppose L is accepted by a uniform polynomial size
circuit family C=(C1,C2,…). Given an input x of length |x|=n,
construct the circuit Cn and evaluate it on input x. Accept iff
Cn(x)=1.
• More carefully, it can be shown that
TIME(f(n)) CIRCUIT-SIZE(f(n)log(f(n)) for proper f(n)
P/poly
• Notation: P/poly = class of languages L that can be
accepted by (in general, nonuniform) circuits of
polynomial size, i.e., there is a constant c and a circuit
family C=(C1,C2,…) with that accepts L.
• Reason for notation: P/poly = languages that can be
accepted by a polynomial time Turing Machine, which for
inputs x of length n can access also an advice string an
of polynomial length (the advice string depends only on
the length n, not on the input x).
– advice = description of the circuit Cn.
c
nsize(C ) O(n )
BPP P/poly
• All (binary) languages in BPP have polynomial size circuits.
• Proof:
Suppose L Î BPP. Recall that we can make the error
probability exponentially small,
In terms of the certificate version of BPP, there is a polynomial
p() and a two-input polynomial-time algorithm V(.,.) such that
for every string x
( ) ( 1)2 , eg. 2poly n n
We will show that for every n, there exists a polynomial size
circuit Cn that accepts a string x of length n iff xÎL. The proof
is not efficiently constructive.
(| |) (| | 1) (| |)
(| |) (| | 1) (| |)
| { {0,1} | ( , ) rejects } | 2 2
| { {0,1} | ( , ) accepts } | 2 2
p x x p x
p x x p x
x L y V x y
x L y V x y
BPP P/poly proof
• Claim: There is a certificate y of length p(n) for which V
gives the correct answer for all strings x of length n:
( , ) acceptsx L V x y
Proof: There are 2ⁿ strings x of length n. For each one of
them there are at most bad certificates y (i.e.
certificates for which V gives the wrong answer). So
altogether there are certificates that are bad
for some x at least ½ the certificates are good for all x
( ) ( 1)2p n n
( ) 1 ( )2 2 2p n p n
• If we knew such a good certificate y*, we could decide whether
xÎL by running V on input x, y*.
• Map V to a circuit and set the input bits corresponding to the
certificate according to y* circuit Cn