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

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