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

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 wA. 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