Cook-Levin Theorem in NP-Completeness

Computational Complexity Theory

Lecture 4:  

NTMs,  Search vs Decision,

                Class co-NP

Indian Institute of Science

Recap:  Cook-Levin theorem



Definition.

 Let

 SAT 

be the language consisting of all

satisfiable CNF formulae.



Theorem.

(Cook-Levin) 

SAT 

is NP-complete.

Recap:  Cook-Levin theorem



Definition.

 Let

 SAT 

be the language consisting of all

satisfiable CNF formulae.



Theorem.

(Cook-Levin) 

SAT 

is NP-complete.



Theorem.

  Let 

N

 be a DTM that runs in time 

T(n)

 on

inputs of length 

n

, and outputs 

0

/

1

. Then,

1.

There’s a 

boolean circuit

Ψ

 of size 

poly

(T(n))

such that 

Ψ(u) = N(u)

, for every 

u

 of length 

n

.

2.

Ψ

 is computable in time 

poly

(T(n))

 from 

M

.

…if 

T(n)

 is time constructible!

Cook-Levin theorem:  Proof

….

cell j

q

i,j

       b

i,j

     h

i,j

i

….

Main insight:

  Computation is 

local

; i.e. every step of

computation 

looks at 

and 

changes

 only constantly

many bits.

….

cell j

q

i-1,j

    b

i-1,j   

 h

i-1,j

i-1

….

q

i-1,j-1

 b

i-1,j-1  

h

i-1,j-1

q

i-1,j+1

 b

i-1,j+1   

h

i-1,j+1

cell j-1

cell j+1

Cook-Levin theorem:  Proof

….

q

i,j

       b

i,j

     h

i,j

i

….

Main insight:

  Computation is 

local

; i.e. every step of

computation 

looks at 

and 

changes

 only constantly

many bits.

….

cell j

q

i-1,j

    b

i-1,j   

 h

i-1,j

i-1

….

q

i-1,j-1

 b

i-1,j-1  

h

i-1,j-1

q

i-1,j+1

 b

i-1,j+1   

h

i-1,j+1

cell j-1

cell j+1

…

Recap:  Cook-Levin theorem



Let 

L

∈

NP

. 

We intend to come up with a polynomial

time computable function 

f:  x        ϕ

x

   s.t.,

x 

∈

 L

ϕ

x

∈

 SAT



Language 

L

 has a poly-time verifier 

M 

such that

x

∈

L         

∃

u 

∈

{0,1}

p(|x|)

s.t.

  M(x, u) = 1

Recap:  Cook-Levin theorem



Let 

L

∈

NP

. 

We intend to come up with a polynomial

time computable function 

f:  x        ϕ

x

   s.t.,

x 

∈

 L

ϕ

x

∈

 SAT



Language 

L

 has a poly-time verifier 

M 

such that

x

∈

L         

∃

u 

∈

{0,1}

p(|x|)

s.t.

 Ψ

x

(u) = 1

Recap:  Cook-Levin theorem



Let 

L

∈

NP

. 

We intend to come up with a polynomial

time computable function 

f:  x        ϕ

x

   s.t.,

x 

∈

 L

ϕ

x

∈

 SAT



Language 

L

 has a poly-time verifier 

M 

such that

x

∈

L        Ψ

x

(u) 

is satisfiable

Recap:  Cook-Levin theorem



Let 

L

∈

NP

. 

We intend to come up with a polynomial

time computable function 

f:  x        ϕ

x

   s.t.,

x 

∈

 L

ϕ

x

∈

 SAT



Language 

L

 has a poly-time verifier 

M 

such that

x

∈

L        Ψ

x

(u) 

is satisfiable

a poly-size circuit but not a poly-size CNF

Recap:  Cook-Levin theorem



Let 

L

∈

NP

. 

We intend to come up with a polynomial

time computable function 

f:  x        ϕ

x

   s.t.,

x 

∈

 L

ϕ

x

∈

 SAT



Language 

L

 has a poly-time verifier 

M 

such that

x

∈

L        Ψ

x

(u) 

is satisfiable

may not be possible to convert a

Ψ

x 

to a

poly-size

 CNF 

ϕ

x

such that 

Ψ

x

(u) = ϕ

x

(u).

Recap:  Cook-Levin theorem



From circuit to CNF.

  From circuit 

Ψ

construct a CNF 

ϕ 

by introducing some 

extra variables

 such that

Ψ(u) = N(u) = 1

  iff  

ϕ(u, 

“

extra variables

”

) 

is satisfiable.

Recap:  Cook-Levin theorem



From circuit to CNF.

  From circuit 

Ψ

construct a CNF 

ϕ 

by introducing some 

extra variables

v

 such that

Ψ(u) = N(u) = 1

  iff  

ϕ(u, 

v

) 

is satisfiable.



Language 

L

 has a poly-time verifier 

M 

such that

x

∈

L         

∃

u 

∈

{0,1}

p(|x|)

s.t.

 Ψ

x

(u) = 1

Recap:  Cook-Levin theorem



From circuit to CNF.

  From circuit 

Ψ

construct a CNF 

ϕ 

by introducing some 

extra variables

v

 such that

Ψ(u) = N(u) = 1

  iff  

ϕ(u, 

v

) 

is satisfiable.



Language 

L

 has a poly-time verifier 

M 

such that

x

∈

L         

∃

u 

∈

{0,1}

p(|x|)

s.t.

 ϕ

x

(u, 

v

) 

is satisfiable

Recap:  Cook-Levin theorem



From circuit to CNF.

  From circuit 

Ψ

construct a CNF 

ϕ 

by introducing some 

extra variables

v

 such that

Ψ(u) = N(u) = 1

  iff  

ϕ(u, 

v

) 

is satisfiable.



Language 

L

 has a poly-time verifier 

M 

such that

      x

∈

L         ϕ

x

(u, 

v

) 

is satisfiable



ϕ

x

 is computable in time 

poly

(T(n))

 from 

M

.

…if 

T(n)

 is time constructible!

Recap:  Cook-Levin theorem



From circuit to CNF.

  From circuit 

Ψ

construct a CNF 

ϕ 

by introducing some 

extra variables

v

 such that

Ψ(u) = N(u) = 1

  iff  

ϕ(u, 

v

) 

is satisfiable.



Language 

L

 has a poly-time verifier 

M 

such that

      x

∈

L         ϕ

x

(u, 

v

) 

is satisfiable



A satisfying assignment 

(u, 

v

) 

for 

ϕ

x 

trivially gives a

certificate 

u 

such that 

M(x, u) = 1

.

NTM:  An alternate characterization of NP

Nondeterministic Turing Machines



A 

nondeterministic Turing machine

 is like a deterministic

Turing machines but with two transition functions.



It is formally defined by a tuple 

(Γ, Q, δ

0 

, δ

1

). 

It has a

special state

 q

accept

in addition to 

q

start

and

 q

halt

.

Nondeterministic Turing Machines



A 

nondeterministic Turing machine

 is like a deterministic

Turing machines but with two transition functions.



It is formally defined by a tuple 

(Γ, Q, δ

0 

, δ

1

). 

It has a

special state

 q

accept

in addition to 

q

start

and

 q

halt

.



At every step of computation, the machine applies

one of two functions 

δ

0 

and 

δ

1

arbitrarily

.

this is different from 

randomly

Nondeterministic Turing Machines



A 

nondeterministic Turing machine

 is like a deterministic

Turing machines but with two transition functions.



It is formally defined by a tuple 

(Γ, Q, δ

0 

, δ

1

). 

It has a

special state

 q

accept

in addition to 

q

start

and

 q

halt

.



At every step of computation, the machine applies

one of two functions 

δ

0 

and 

δ

1

arbitrarily

.

also called 

nondeterministically

Nondeterministic Turing Machines



A 

nondeterministic Turing machine

 is like a deterministic

Turing machines but with two transition functions.



It is formally defined by a tuple 

(Γ, Q, δ

0 

, δ

1

). 

It has a

special state

 q

accept

in addition to 

q

start

and

 q

halt

.



At every step of computation, the machine applies

one of two functions 

δ

0 

and 

δ

1

arbitrarily

.



Unlike DTMs,  NTMs are not intended to be

physically realizable (because of the arbitrary nature

of application of the transition functions).

Nondeterministic Turing Machines



Definition.

  An NTM 

M

accepts

 a string 

x

∈

{0,1}* 

iff on

input 

x

 there 

exists

 a sequence of applications of the

transition functions 

δ

0 

and 

δ

1

 (beginning from the

start configuration) that makes 

M 

reach 

q

accept

.



Defintion

.  An NTM 

M

decides

 a language 

L 

⊆

 {0,1}* 

if



M

 accepts 

x

x

∈

L



On every sequence of applications of the transition

functions on input 

x

, 

M 

either reaches 

q

accept

or

 q

halt

.

Nondeterministic Turing Machines



Definition.

  An NTM 

M

accepts

 a string 

x

∈

{0,1}* 

iff on

input 

x

 there 

exists

 a sequence of applications of the

transition functions 

δ

0 

and 

δ

1

 (beginning from the

start configuration) that makes 

M 

reach 

q

accept

.



Defintion

.  An NTM 

M

decides

 a language 

L 

⊆

 {0,1}* 

if



M

 accepts 

x

x

∈

L



On every sequence of applications of the transition

functions on input 

x

, 

M 

either reaches 

q

accept

or

 q

halt

.

remember in this course we’ll always be dealing with TMs

that halt on every input.

Nondeterministic Turing Machines



Definition.

  An NTM 

M

accepts

 a string 

x

∈

{0,1}* 

iff on

input 

x

 there 

exists

 a sequence of applications of the

transition functions 

δ

0 

and 

δ

1

 (beginning from the

start configuration) that makes 

M 

reach 

q

accept

.



Defintion

.  An NTM 

M

decides

L 

in 

T(|x|)

 time if



M

 accepts 

x

x

∈

L



On 

every sequence 

of applications of the transition

functions on input 

x

, 

M 

either reaches 

q

accept

or

 q

halt

within

 T(|x|) 

steps of computation.

Class NTIME



Definition.

  A language 

L

 is in 

NTIME(T(n))

 if there’s

an NTM 

M

 that decides 

L

 in 

c. T(n) 

time on inputs of

length 

n, 

where 

c

 is a constant

.

Alternate characterization of NP



Definition.

  A language 

L

 is in 

NTIME(T(n))

 if there’s

an NTM 

M

 that decides 

L

 in 

c. T(n) 

time on inputs of

length 

n, 

where 

c

 is a constant

.



Theorem.

NP = 

∪

 NTIME (n

c

).

   Proof sketch:  

Let 

L

 be a language in 

NP

.  Then, there’s

a poly-time verifier 

M

 s.t,

        x

∈

L         

∃

u 

∈

{0,1}

p(|x|)

s.t.

  M(x, u) = 1

c > 0

Alternate characterization of NP



Definition.

  A language 

L

 is in 

NTIME(T(n))

 if there’s

an NTM 

M

 that decides 

L

 in 

c. T(n) 

time on inputs of

length 

n, 

where 

c

 is a constant

.



Theorem.

NP = 

∪

 NTIME (n

c

).

   Proof sketch:  

Let 

L

 be a language in 

NP

.  Then, there’s

a poly-time verifier 

M

 s.t,

        x

∈

L         

∃

u 

∈

{0,1}

p(|x|)

s.t.

  M(x, u) = 1

Think of an NTM 

M’ 

that on input 

x

, at first 

guesses

 a 

u

∈

{0,1}

p(|x|)

by applying 

δ

0 

and 

δ

1

 nondeterministically

c > 0

Alternate characterization of NP



Definition.

  A language 

L

 is in 

NTIME(T(n))

 if there’s

an NTM 

M

 that decides 

L

 in 

c. T(n) 

time on inputs of

length 

n, 

where 

c

 is a constant

.



Theorem.

NP = 

∪

 NTIME (n

c

).

   Proof sketch:  

Let 

L

 be a language in 

NP

.  Then, there’s

a poly-time verifier 

M

 s.t,

        x

∈

L         

∃

u 

∈

{0,1}

p(|x|)

s.t.

  M(x, u) = 1

…. and then simulates 

M

 on 

(x, u) 

to 

verify

 M(x,u) = 1

.

c > 0

Alternate characterization of NP



Definition.

  A language 

L

 is in 

NTIME(T(n))

 if there’s

an NTM 

M

 that decides 

L

 in 

c. T(n) 

time on inputs of

length 

n, 

where 

c

 is a constant

.



Theorem.

NP = 

∪

 NTIME (n

c

).

   Proof sketch:  

Let 

L

 be in 

NTIME (n

c

)

.  Then, there’s an

NTM 

M’

 that decides 

L

 in 

p(n) = O(n

c

)

 time.    (|x| = n)

c > 0

Alternate characterization of NP



Definition.

  A language 

L

 is in 

NTIME(T(n))

 if there’s

an NTM 

M

 that decides 

L

 in 

c. T(n) 

time on inputs of

length 

n, 

where 

c

 is a constant

.



Theorem.

NP = 

∪

 NTIME (n

c

).

   Proof sketch:  

Let 

L

 be in 

NTIME (n

c

)

.  Then, there’s an

NTM 

M’

 that decides 

L

 in 

p(n) = O(n

c

)

 time.    (|x| = n) 

Think of a verifier 

M

 that takes 

x

 and 

u 

∈

{0,1}

p(n)

 as

input,

c > 0

Alternate characterization of NP



Definition.

  A language 

L

 is in 

NTIME(T(n))

 if there’s

an NTM 

M

 that decides 

L

 in 

c. T(n) 

time on inputs of

length 

n, 

where 

c

 is a constant

.



Theorem.

NP = 

∪

 NTIME (n

c

).

   Proof sketch:  

Let 

L

 be in 

NTIME (n

c

)

.  Then, there’s an

NTM 

M’

 that decides 

L

 in 

p(n) = O(n

c

)

 time.    (|x| = n) 

Think of a verifier 

M

 that takes 

x

 and 

u 

∈

{0,1}

p(n)

 as

input, and simulates 

M’

 on 

x

 with 

u 

as the sequence of

choices for applying 

δ

0 

and 

δ

1

 .

c > 0

Search versus Decision

Search version of NP problems



Recall:   A language 

L 

⊆

 {0,1}* 

is in 

NP 

if



 There’s a 

poly-time verifier 

M

 such that



x

∈

L 

iff there’s a 

poly-size certificate 

u 

s.t 

M(x,u) = 1

•

Search version of L:  

Given an input

 x 

∈

 {0,1}

*

, 

find

 a 

u

∈

{0,1}

p(|x|)

such that 

M(x,u) = 1

, if such a 

u 

exists.

Search version of NP problems



Recall:   A language 

L 

⊆

 {0,1}* 

is in 

NP 

if



 There’s a 

poly-time verifier 

M

 such that



x

∈

L 

iff there’s a 

poly-size certificate 

u 

s.t 

M(x,u) = 1

•

Search version of L:  

Given an input

 x 

∈

 {0,1}

*

, 

find

 a 

u

∈

{0,1}

p(|x|)

such that 

M(x,u) = 1

, if such a 

u 

exists.

•

Example:  

Given a 3CNF 

ϕ

, find a satisfying assignment

for

 ϕ 

if such an assignment exists.

Decision versus Search



Is the search version of an NP-problem more difficult

than the corresponding decision version?

Decision versus Search



Is the search version of an NP-problem more difficult

than the corresponding decision version?



Theorem.

 Let 

L 

⊆

 {0,1}* 

be 

NP-complete

. Then, the

search version of 

L

 can be solved in poly-time if and

only if the decision version can be solved in poly-time.

Decision versus Search



Is the search version of an NP-problem more difficult

than the corresponding decision version?



Theorem.

 Let 

L 

⊆

 {0,1}* 

be 

NP-complete

. Then, the

search version of 

L

 can be solved in poly-time if and

only if the decision version can be solved in poly-time.



Proof.

   (search       decision)  Obvious.

Decision versus Search



Is the search version of an NP-problem more difficult

than the corresponding decision version?



Theorem.

 Let 

L 

⊆

 {0,1}* 

be 

NP-complete

. Then, the

search version of 

L

 can be solved in poly-time if and

only if the decision version can be solved in poly-time.



Proof.

   (decision        search)  We’ll prove this for

L = SAT

 first.

SAT is 

downward self-reducible



Proof.

  (decision      search)  Let 

L = SAT

,  and 

A

 be a

poly-time algorithm to decide if 

ϕ(x

1

,…,x

n

) 

is satisfiable.

SAT is 

downward self-reducible



Proof.

  (decision      search)  Let 

L = SAT

,  and 

A

 be a

poly-time algorithm to decide if 

ϕ(x

1

,…,x

n

) 

is satisfiable.

ϕ(x

1

,…,x

n

)

SAT is 

downward self-reducible



Proof.

  (decision      search)  Let 

L = SAT

,  and 

A

 be a

poly-time algorithm to decide if 

ϕ(x

1

,…,x

n

) 

is satisfiable.

ϕ(x

1

,…,x

n

)

A(ϕ) = 

Y

SAT is 

downward self-reducible



Proof.

  (decision      search)  Let 

L = SAT

,  and 

A

 be a

poly-time algorithm to decide if 

ϕ(x

1

,…,x

n

) 

is satisfiable.

ϕ(x

1

,…,x

n

)

A(ϕ) = 

Y

ϕ(

0

,…,x

n

)

SAT is 

downward self-reducible



Proof.

  (decision      search)  Let 

L = SAT

,  and 

A

 be a

poly-time algorithm to decide if 

ϕ(x

1

,…,x

n

) 

is satisfiable.

ϕ(x

1

,…,x

n

)

A(ϕ) = 

Y

ϕ(

0

,…,x

n

)

A( ϕ(0,..) ) = 

N

SAT is 

downward self-reducible



Proof.

  (decision      search)  Let 

L = SAT

,  and 

A

 be a

poly-time algorithm to decide if 

ϕ(x

1

,…,x

n

) 

is satisfiable.

ϕ(x

1

,…,x

n

)

A(ϕ) = 

Y

ϕ(

0

,…,x

n

)

A( ϕ(0,..) ) = 

N

ϕ(

1

,…,x

n

)

SAT is 

downward self-reducible



Proof.

  (decision      search)  Let 

L = SAT

,  and 

A

 be a

poly-time algorithm to decide if 

ϕ(x

1

,…,x

n

) 

is satisfiable.

ϕ(x

1

,…,x

n

)

A(ϕ) = 

Y

ϕ(

0

,…,x

n

)

A( ϕ(0,..) ) = 

N

ϕ(

1

,…,x

n

)

 A( ϕ(1,..) ) = 

Y

SAT is 

downward self-reducible



Proof.

  (decision      search)  Let 

L = SAT

,  and 

A

 be a

poly-time algorithm to decide if 

ϕ(x

1

,…,x

n

) 

is satisfiable.

ϕ(x

1

,…,x

n

)

A(ϕ) = 

Y

ϕ(

0

,…,x

n

)

A( ϕ(0,..) ) = 

N

ϕ(

1

,…,x

n

)

 A( ϕ(1,..) ) = 

Y

ϕ(

1

,

0

,…,x

n

)

SAT is 

downward self-reducible



Proof.

  (decision      search)  Let 

L = SAT

,  and 

A

 be a

poly-time algorithm to decide if 

ϕ(x

1

,…,x

n

) 

is satisfiable.

ϕ(x

1

,…,x

n

)

A(ϕ) = 

Y

ϕ(

0

,…,x

n

)

A( ϕ(0,..) ) = 

N

ϕ(

1

,…,x

n

)

 A( ϕ(1,..) ) = 

Y

ϕ(

1

,

0

,…,x

n

)

 A( ϕ(1,0,..) ) = 

Y

SAT is 

downward self-reducible



Proof.

  (decision      search)  Let 

L = SAT

,  and 

A

 be a

poly-time algorithm to decide if 

ϕ(x

1

,…,x

n

) 

is satisfiable.

ϕ(x

1

,…,x

n

)

A(ϕ) = 

Y

ϕ(

0

,…,x

n

)

A( ϕ(0,..) ) = 

N

ϕ(

1

,…,x

n

)

 A( ϕ(1,..) ) = 

Y

ϕ(

1

,

0

,…,x

n

)

 A( ϕ(1,0,..) ) = 

Y

ϕ(

1

,

0

,

0

,…,x

n

)

SAT is 

downward self-reducible



Proof.

  (decision      search)  Let 

L = SAT

,  and 

A

 be a

poly-time algorithm to decide if 

ϕ(x

1

,…,x

n

) 

is satisfiable.

ϕ(x

1

,…,x

n

)

A(ϕ) = 

Y

ϕ(

0

,…,x

n

)

A( ϕ(0,..) ) = 

N

ϕ(

1

,…,x

n

)

 A( ϕ(1,..) ) = 

Y

ϕ(

1

,

0

,…,x

n

)

 A( ϕ(1,0,..) ) = 

Y

ϕ(

1

,

0

,

0

,…,x

n

)

 A( ϕ(1,0,0...) ) = 

N

SAT is 

downward self-reducible



Proof.

  (decision      search)  Let 

L = SAT

,  and 

A

 be a

poly-time algorithm to decide if 

ϕ(x

1

,…,x

n

) 

is satisfiable.

ϕ(x

1

,…,x

n

)

A(ϕ) = 

Y

ϕ(

0

,…,x

n

)

A( ϕ(0,..) ) = 

N

ϕ(

1

,…,x

n

)

 A( ϕ(1,..) ) = 

Y

ϕ(

1

,

0

,…,x

n

)

 A( ϕ(1,0,..) ) = 

Y

ϕ(

1

,

0

,

0

,…,x

n

)

 A( ϕ(1,0,0...) ) = 

N

ϕ(

1

,

0

,

1

,…,x

n

)

SAT is 

downward self-reducible



Proof.

  (decision      search)  Let 

L = SAT

,  and 

A

 be a

poly-time algorithm to decide if 

ϕ(x

1

,…,x

n

) 

is satisfiable.

ϕ(x

1

,…,x

n

)

A(ϕ) = 

Y

ϕ(

0

,…,x

n

)

A( ϕ(0,..) ) = 

N

ϕ(

1

,…,x

n

)

 A( ϕ(1,..) ) = 

Y

ϕ(

1

,

0

,…,x

n

)

 A( ϕ(1,0,..) ) = 

Y

ϕ(

1

,

0

,

0

,…,x

n

)

 A( ϕ(1,0,0...) ) = 

N

ϕ(

1

,

0

,

1

,…,x

n

)

 A( ϕ(1,0,0...) ) = 

Y

SAT is 

downward self-reducible



Proof.

  (decision      search)  Let 

L = SAT

,  and 

A

 be a

poly-time algorithm to decide if 

ϕ(x

1

,…,x

n

) 

is satisfiable.

ϕ(x

1

,…,x

n

)

A(ϕ) = 

Y

ϕ(

0

,…,x

n

)

A( ϕ(0,..) ) = 

N

ϕ(

1

,…,x

n

)

 A( ϕ(1,..) ) = 

Y

ϕ(

1

,

0

,…,x

n

)

 A( ϕ(1,0,..) ) = 

Y

ϕ(

1

,

0

,

0

,…,x

n

)

 A( ϕ(1,0,0...) ) = 

N

ϕ(

1

,

0

,

1

,…,x

n

)

 A( ϕ(1,0,0...) ) = 

Y

.

.

.

.

SAT is 

downward self-reducible



Proof.

  (decision      search)  Let 

L = SAT

,  and 

A

 be a

poly-time algorithm to decide if 

ϕ(x

1

,…,x

n

) 

is satisfiable.

ϕ(x

1

,…,x

n

)

A(ϕ) = 

Y

ϕ(

0

,…,x

n

)

A( ϕ(0,..) ) = 

N

ϕ(

1

,…,x

n

)

 A( ϕ(1,..) ) = 

Y

ϕ(

1

,

0

,…,x

n

)

 A( ϕ(1,0,..) ) = 

Y

ϕ(

1

,

0

,

0

,…,x

n

)

 A( ϕ(1,0,0...) ) = 

N

ϕ(

1

,

0

,

1

,…,x

n

)

 A( ϕ(1,0,0...) ) = 

Y

.

.

.

.

SAT is 

downward self-reducible



Proof.

  (decision      search)  Let 

L = SAT

,  and 

A

 be a

poly-time algorithm to decide if 

ϕ(x

1

,…,x

n

) 

is satisfiable.



We can find a satisfying assignment of 

ϕ 

with at most 

2n

calls to

 A.

Decision 

≡

 Search for NPC problems



Proof.

 (decision       search)  Let 

L 

be NP-complete,  and

B

 be a poly-time algorithm to decide if 

x

∈

L.

Decision 

≡

 Search for NPC problems



Proof.

 (decision       search)  Let 

L 

be NP-complete,  and

B

 be a poly-time algorithm to decide if 

x

∈

L.

SAT  ≤

p

  L

L  ≤

p

  SAT

Decision 

≡

 Search for NPC problems



Proof.

 (decision       search)  Let 

L 

be NP-complete,  and

B

 be a poly-time algorithm to decide if 

x

∈

L.

SAT  ≤

p

  L

L  ≤

p

  SAT

x             

ϕ

x

Decision 

≡

 Search for NPC problems



Proof.

 (decision       search)  Let 

L 

be NP-complete,  and

B

 be a poly-time algorithm to decide if 

x

∈

L.

SAT  ≤

p

  L

L  ≤

p

  SAT

x             

ϕ

x

Since Cook-Levin theorem

actually gives a 

Levin-reduction

from 

x

 to 

ϕ

x

,

we can find a

certificate of 

x

 from a

certificate of 

ϕ

x

.

Decision 

≡

 Search for NPC problems



Proof.

 (decision       search)  Let 

L 

be NP-complete,  and

B

 be a poly-time algorithm to decide if 

x

∈

L.

SAT  ≤

p

  L

L  ≤

p

  SAT

x             

ϕ

x

How to find a certificate of 

ϕ

x

using algorithm

 B 

?

Decision 

≡

 Search for NPC problems



Proof.

 (decision       search)  Let 

L 

be NP-complete,  and

B

 be a poly-time algorithm to decide if 

x

∈

L.

SAT  ≤

p

  L

L  ≤

p

  SAT

x             

ϕ

x

How to find a certificate of 

ϕ

x

using algorithm

 B 

?

      … we know how to using  

A

,

a poly-time decider for 

SAT

Decision 

≡

 Search for NPC problems



Proof.

 (decision       search)  Let 

L 

be NP-complete,  and

B

 be a poly-time algorithm to decide if 

x

∈

L.

SAT  ≤

p

  L

L  ≤

p

  SAT

x             

ϕ

x

How to find a certificate of 

ϕ

x

using algorithm

 B 

?

      … we know how to using  

A

,

a poly-time decider for 

SAT

ϕ           f(ϕ)

Decision 

≡

 Search for NPC problems



Proof.

 (decision       search)  Let 

L 

be NP-complete,  and

B

 be a poly-time algorithm to decide if 

x

∈

L.

SAT  ≤

p

  L

L  ≤

p

  SAT

x             

ϕ

x

How to find a certificate of 

ϕ

x

using algorithm

 B 

?

      Take    

A

(ϕ)  =  

B

( f(ϕ) )

ϕ           f(ϕ)

Decision versus Search



Is 

search

 equivalent to 

decision

 for every NP problem?

Decision versus Search



Is 

search

 equivalent to 

decision

 for every NP problem?

Probably not!

Decision versus Search



Is 

search

 equivalent to 

decision

 for every NP problem?



Let 

EE = 

∪

 DTIME (2

c.2  

) 

and

      N

EE = 

∪

 NTIME (2

c.2  

)

c ≥ 0

n

c ≥ 0

n

Doubly exponential

analogues of 

P

 and 

NP

Decision versus Search



Is 

search

 equivalent to 

decision

 for every NP problem?



Theorem. 

(Bellare-Goldwasser)

If 

EE ≠ NEE 

then there’s a

language in 

NP

 for which search does not reduce to

decision.

Class co-NP



Definition.   

For every 

L 

⊆

 {0,1}* 

let

 L = {0,1}* \ L

.

   A language 

L

 is in 

co-NP 

if  

L

 is in 

NP

.



Example.

SAT  =

  {

ϕ : ϕ 

is 

not

 satisfiable}.

Class co-NP



Definition.   

For every 

L 

⊆

 {0,1}* 

let

 L = {0,1}* \ L

.

   A language 

L

 is in 

co-NP 

if  

L

 is in 

NP

.



Example.

SAT  =

  {

ϕ : ϕ 

is 

not

 satisfiable}.



Note: 

co-NP

 is 

not

 complement of 

NP

. Every language

in 

P

 is in both 

NP

 and 

co-NP

.

Class co-NP



Definition.   

For every 

L 

⊆

 {0,1}* 

let

 L = {0,1}* \ L

.

   A language 

L

 is in 

co-NP 

if  

L

 is in 

NP

.



Example.

SAT  =

  {

ϕ : ϕ 

is 

not

 satisfiable}.

NP

co-NP

P

Class co-NP :  Alternate definition



Recall, a language 

L 

⊆

 {0,1}* 

is in 

NP 

if 

there’s a 

poly-time

verifier 

M

 such that

x

∈

L        

∃

u 

∈

{0,1}

p(|x|)

s.t.

  M(x, u) = 1

Class co-NP :  Alternate definition



Recall, a language 

L 

⊆

 {0,1}* 

is in 

NP 

if 

there’s a 

poly-time

verifier 

M

 such that

x

∈

L        

∃

u 

∈

{0,1}

p(|x|)

s.t.

  M(x, u) = 1

            x

∈

L        

∀

u 

∈

{0,1}

p(|x|)

s.t.

  M(x, u) = 0

Class co-NP :  Alternate definition



Recall, a language 

L 

⊆

 {0,1}* 

is in 

NP 

if 

there’s a 

poly-time

verifier 

M

 such that

x

∈

L        

∃

u 

∈

{0,1}

p(|x|)

s.t.

  M(x, u) = 1

            x

∈

L        

∀

u 

∈

{0,1}

p(|x|)

s.t.

  M(x, u) = 0

            x

∈

L        

∀

u 

∈

{0,1}

p(|x|)

s.t.

  M(x, u) = 1

M 

outputs the

opposite

 of 

M

Class co-NP :  Alternate definition



Recall, a language 

L 

⊆

 {0,1}* 

is in 

NP 

if 

there’s a 

poly-time

verifier 

M

 such that

x

∈

L        

∃

u 

∈

{0,1}

p(|x|)

s.t.

  M(x, u) = 1

            x

∈

L        

∀

u 

∈

{0,1}

p(|x|)

s.t.

  M(x, u) = 0

            x

∈

L        

∀

u 

∈

{0,1}

p(|x|)

s.t.

  M(x, u) = 1

M 

is a poly-time TM

Class co-NP :  Alternate definition



Recall, a language 

L 

⊆

 {0,1}* 

is in 

NP 

if 

there’s a 

poly-time

verifier 

M

 such that

x

∈

L        

∃

u 

∈

{0,1}

p(|x|)

s.t.

  M(x, u) = 1

            x

∈

L        

∀

u 

∈

{0,1}

p(|x|)

s.t.

  M(x, u) = 0

            x

∈

L        

∀

u 

∈

{0,1}

p(|x|)

s.t.

  M(x, u) = 1

is in 

co-NP

Class co-NP :  Alternate definition



Recall, a language 

L 

⊆

 {0,1}* 

is in 

NP 

if 

there’s a 

poly-time

verifier 

M

 such that

x

∈

L        

∃

u 

∈

{0,1}

p(|x|)

s.t.

  M(x, u) = 1

            x

∈

L        

∀

u 

∈

{0,1}

p(|x|)

s.t.

  M(x, u) = 0

            x

∈

L        

∀

u 

∈

{0,1}

p(|x|)

s.t.

  M(x, u) = 1



Definition.

  A language 

L 

⊆

 {0,1}* 

is in 

co-NP 

if there’s a

poly-time TM 

M

 such that

x

∈

L        

∀

u 

∈

{0,1}

p(|x|)

s.t.

  M(x, u) = 1

co-NP-completeness



Definition.

  A language 

L’ 

⊆

 {0,1}* 

is 

co-NP-complete

if



 L’ is in 

co-NP



 Every language

 L 

in

co-NP 

is polynomial-time (Karp)

reducible to

 L’

.

•

Theorem.

SAT 

is co-NP-complete.

co-NP-completeness



Definition.

  A language 

L’ 

⊆

 {0,1}* 

is 

co-NP-complete

if



 L’ is in 

co-NP



 Every language

 L 

in

co-NP 

is polynomial-time (Karp)

reducible to

 L’

.

•

Theorem.

SAT 

is co-NP-complete.

   Proof.

  Let   

L 

∈

co-NP

.

   Then

L

∈

NP

co-NP-completeness



Definition.

  A language 

L’ 

⊆

 {0,1}* 

is 

co-NP-complete

if



 L’ is in 

co-NP



 Every language

 L 

in

co-NP 

is polynomial-time (Karp)

reducible to

 L’

.

•

Theorem.

SAT 

is co-NP-complete.

   Proof.

  Let   

L 

∈

co-NP

.

   Then

L

∈

NP

L  ≤

p

 SAT

co-NP-completeness



Definition.

  A language 

L’ 

⊆

 {0,1}* 

is 

co-NP-complete

if



 L’ is in 

co-NP



 Every language

 L 

in

co-NP 

is polynomial-time (Karp)

reducible to

 L’

.

•

Theorem.

SAT 

is co-NP-complete.

   Proof.

  Let   

L 

∈

co-NP

.

   Then

L

∈

NP

L  ≤

p

 SAT

                     L  ≤

p

 SAT

co-NP-completeness



Definition.

  A language 

L’ 

⊆

 {0,1}* 

is 

co-NP-complete

if



 L’ is in 

co-NP



 Every language

 L 

in

co-NP 

is polynomial-time (Karp)

reducible to

 L’

.

•

Theorem.

  Let

TAUTOLOGY = 

{

ϕ :  

every assignment satisfies

 ϕ 

}.

TAUTOLOGY

 is 

co-NP

 complete.

Proof.

   Similar 

(homework)

Class EXP



Definition.  

Class 

EXP

 is the exponential time

analogue of class 

P

.

EXP  =  

∪

 DTIME ( 2

n   

)

c

c ≥ 1

Class EXP



Definition.  

Class 

EXP

 is the exponential time

analogue of class 

P

.

EXP  =  

∪

 DTIME ( 2

n   

)



Observation.

   P  

⊆

 NP  

⊆

  EXP

c

c ≥ 1

Class EXP



Definition.  

Class 

EXP

 is the exponential time

analogue of class 

P

.

EXP  =  

∪

 DTIME ( 2

n   

)



Observation.

   P  

⊆

 NP  

⊆

  EXP

c

c ≥ 1

NP

co-NP

P

EXP

Class EXP



Definition.  

Class 

EXP

 is the exponential time

analogue of class 

P

.

EXP  =  

∪

 DTIME ( 2

n   

)



Observation.

   P  

⊆

 NP  

⊆

  EXP



Exponential Time Hypothesis. 

(Impagliazzo & Paturi)

Any algorithm for 

3-SAT 

takes time 

Ω(2

δ.n

)

, where 

δ

 is

a constant and 

n

 is the input size.

c

c ≥ 1

Class EXP



Definition.  

Class 

EXP

 is the exponential time

analogue of class 

P

.

EXP  =  

∪

 DTIME ( 2

n   

)



Observation.

   P  

⊆

 NP  

⊆

  EXP



Exponential Time Hypothesis. 

(Impagliazzo & Paturi)

Any algorithm for 

3-SAT 

takes time 

Ω(2

δ.n

)

, where 

δ

 is

a constant and 

n

 is the input size.

c

c ≥ 1

ETH          

P ≠ NP