Microsoft PowerPoint – lecture20 [Compatibility Mode]
COMS4236: Introduction to
Computational Complexity
Spring 2018
Mihalis Yannakakis
Lecture 20, 3/29/18
Exponential Circuit Size
• Recall that every Boolean function has an exponential size
circuit (in fact, formula) every binary language has at
most exponential circuit size complexity
(in contrast to the fact that there are languages that have
much higher time complexity)
• There are Boolean functions that require exponential size
circuits, in fact almost all of them do.
Proof: There are Boolean functions with n inputs and
1 output. A circuit with s gates and wires can be specified
by specifying for each gate its type (2 bits), and for each
wire the endpoints (2log(n+s) bits) s(2+2log(n+s)) bits
total there are ≤ s2s(2+2log(n+s)) circuits of size at most s.
This is less than if s is less than .
22
n
22
n
2 2n n
NP P/poly ?
• Conjecture: NP-complete problems cannot be decided by
polynomial size circuits, probably require exponential size.
• Although we know that most Boolean functions/languages
require exponential size circuits, no such bound for any
concrete, natural problem; in fact, nothing better than linear
lower bounds.
• Known: There is a language with exponential space
complexity that requires exponential size circuits (Proof by
diagonalization – HW exercise).
Monotone Problems
• Monotone Boolean function f: If x≥x’ (bitwise comparison)
then f(x)≥f(x’)
• Monotone problem: corresponds to family of monotone
Boolean functions.
• Examples:
• Graph Reachabiity, where graph is represented by its
adjacency matrix: one input bit for each pair (u,v) of nodes,
bit =1 if there is edge, 0 otherwise
• Hamiltonicity, same representation
• n/2-Clique: Given graph, does it have a clique with n/2
nodes?
• Perfect matching in bipartite or in general graphs.
Represent bipartite graphs with the two parts L=(l1,…,ln),
R=(r1,…,rn) by n² input bits, one bit for each pair (li,rj)
Monotone Circuits
• No NOT gates: compute monotone functions
• Does this reduce the power?
• [Razborov] The n/2-Clique problem requires exponential
size monotone circuits.
(Proof: see the book, Chapter 14.4.)
In fact,
• The bipartite perfect matching problem also requires
exponential size monotone circuits.
• The bipartite perfect matching problem ÎP has
polynomial size circuits
exponential gap between the power of general and
monotone circuits
Oracles
• Oracle Turing Machine : A TM extended with an oracle
tape, and special states q? (query state), qyes, qno (answer
states).
• Computations of the TM relative to a language A (the
oracle): when the TM enters q? , in the next step it moves
to qyes if the string w on the oracle tape is in A and it moves
to qno if wA. In other respects, it computes like an
ordinary TM and at the end accepts or rejects the input.
• When we count time, the oracle tests wÎA? take 1 step.
• Notation: = TM M with oracle A
• Oracles are like subroutines, but we don’t count the time
spent in the subroutine calls
?M
AM
Relativized (Oracle) Complexity Classes
• Let C be a (deterministic, nondeterministic, randomized..)
time complexity class, and A a language (“the oracle”)
• If is an oracle TM of the same type and time bound as
C we will say
• Notation:
• = { L(MA) | M? C} = class of languages accepted by
an oracle TM in C with oracle A
• If C,D are complexity classes, then
AC
?M
?M C
?M
{ | }D AC C A D
Properties
for all classes CC C
for any class C and language and its complement A AC C A A
Just flip the answer states qyes, qno of an oracle machine in C
D coDC =C for any classes C, D
for all classes C and languages AAC C
Cook (Turing polynomial-time) reduction
PB = All languages (decision problems) that can be Cook-
reduced to B.
• Cook (Turing polynomial-time) reduction from a problem A
to a problem B: A polynomial-time oracle machine MB for A,
i.e., An algorithm that solves problem A using a subroutine
for problem B and which takes polynomial time, apart from
the subroutine calls.
Notation: TpA B
Broader notion of polynomial-time reduction than the usual
one (which is often called Karp-reduction or “many-one
polynomial-time reduction”): In a Cook reduction we can
call the subroutine for B many times on many different
instances.
Properties
P
P
P P
NP NP
Replace the oracle calls with the polynomial time
computation of the answers
T
pA B A P
B P
BB P P P
PNP
NP 3SAT
NP
P (=P ) contains presumably more than NP (eg. coNP)
and NP contains presumably even more.
We will look at these classes later on.
• = All languages (decision problems) that can be
decided in polynomial time using 3SAT as an oracle.
Includes NP and coNP, and presumably more.
3SATP
3SAT NPP P
Proof: For any oracle AÎNP, we can transform any query
string x for A to a formula for 3SAT that has the same answer
Proofs that Relativize
• Simulation Proofs: Many proofs showing that a
complexity class C another class D by simulating a
machine M in C by a machine N in D, usually “relativize”,
i.e. hold also for oracle machines with the same oracle
• For example, P NP
NP EXPTIME (can simulate nondeterminism with
exponential blowup in time)
• Diagonalization Proofs: Proofs showing that a complexity
class C ≠ another class D by having a machine of D
simulate all machines of C and diagonalize over them,
usually relativize
• For example Time Hierarchy Theorem
P vs NP and Relativization
1. There is an oracle A such that
2. There is an oracle B such that
Methods that relativize cannot resolve the P vs. NP
question one way or the other.
A AP NP
B BP NP
• For every oracle A, obviously
• Let A be a PSPACE-complete language, i.e. a language
A in PSPACE such that all other languages in PSPACE
reduce to A (we will see later several PSPACE-complete
languages).
• Then:
A AP NP for some oracle A
A ANP NPSPACE PSPACE P
A AP NP
because A PSPACE because A is complete
by Savitch’s theorem