BU CS 332 – Theory of Computation
Lecture 20:
• More on NP
Reading:
Sipser Ch 7.3‐7.5
• P vs. NP
Mark Bun April 13, 2020
Goals of complexity theory
Ultimate goal: Classify problems according to their feasibility and inherent computational difficulty
Decision problems which can be solved efficiently
Can we exhibit general classes of problems which are either in or provably not in ?
Some problems provably require exponential time! (Chapter 9)
: A fundamental and practically important class of problems which have defied classification, but nevertheless exhibits important structure ( completeness)
4/13/2020 CS332 ‐ Theory of Computation 2
Nondeterministic Time and NP
4/13/2020 CS332 ‐ Theory of Computation 3
Nondeterministic time
Let
A NTM runs in time if on every input halts on within at most steps on every
,
computational branch
4/13/2020 CS332 ‐ Theory of Computation
4
Deterministic vs. nondeterministic time
Deterministic
Nondeterministic
accept or reject
reject reject
4/13/2020
CS332 ‐ Theory of Computation
5
𝒕𝒏
reject
accept
accept
Deterministic vs. nondeterministic time
Theorem: Let be a function. Every NTM running in time has an equivalent single‐tape TM running in
Finite control
𝑤 ⊔
# 𝑤 3 7
𝑤
nondeterministic choices from tape 3) Address in computation tree
4/13/2020
CS332 ‐ Theory of Computation 6
time
Proof: Simulate NTM by 3‐tape TM
𝑤 𝑤 𝑤 𝑤
Input 𝑤 to 𝑁 (read‐only) Simulation tape (run 𝑁 on 𝑤 using
1 3
Deterministic vs. nondeterministic time
Theorem: Let be a function. Every NTM running in time has an equivalent single‐tape TM running in
time
input
Proof: Simulate NTM by 3‐tape TM • # leaves:
• # nodes:
Running time:
simulation address
To simulate one root‐to‐node path:
Total time:
4/13/2020 CS332 ‐ Theory of Computation
7
Deterministic vs. nondeterministic time
Theorem: Let be a function. Every NTM running in time has an equivalent single‐tape TM running in
time
Proof: Simulate NTM by 3‐tape TM in time
We know that a 3‐tape TM can be simulated by a single‐ tape TM with quadratic overhead, hence we get running time
= ·=
4/13/2020 CS332 ‐ Theory of Computation 8
Difference in time complexity
Extended Church‐Turing Thesis:
At most polynomial difference in running time between all (reasonable) deterministic models
At most exponential difference in running time between deterministic and nondeterministic models
4/13/2020 CS332 ‐ Theory of Computation 9
Nondeterministic time
Let
A NTM runs in time if on every input , halts on within at most steps on every
computational branch
1) Decides , and 2) Runs in time
is a class (i.e., set) of languages:
A language if there exists an NTM that
4/13/2020 CS332 ‐ Theory of Computation 10
NTIME explicitly
A language if there exists an NTM
such that, on every input
∗
1. 2. 3.
Every computational branch of halts in either the accept or reject state within steps
iff there exists an accepting computational branch of on input
input
iff every computational branch of rejects on (or dies with no applicable transitions)
4/13/2020
CS332 ‐ Theory of Computation 11
Complexity class
Definition: is the class of languages decidable in polynomial time on a nondeterministic TM
4/13/2020
CS332 ‐ Theory of Computation 12
Hamiltonian Path
4/13/2020 CS332 ‐ Theory of Computation 13
The following nondeterministic algorithm accepts in time
.
, where , adjacency matrix encoding
On input : (Vertices of are numbers ) 1. Nondeterministically guess a sequence
of numbers
2. Check that number
is a permutation: Every appears exactly once
3.Checkthat
, ,andthereisanedge from every to
4. Accept if all checks pass, otherwise, reject. 4/13/2020 CS332 ‐ Theory of Computation 14
An alternative characterization of
“Languages with polynomial‐time verifiers”
A verifier for a language is a deterministic algorithm such that iff there exists a string such that
accepts
Running time of a verifier is only measured in terms of
is a polynomial‐time verifier if it runs in time polynomial in on every input
(Without loss of generality, is polynomial in , i.e.,
4/13/2020
CS332 ‐ Theory of Computation 15
for some constant )
Certificate :
1. Check that number
is a permutation: Every appears exactly once
2.Checkthat
has a polynomial‐time verifier
Verifier :
On input : (Vertices of are numbers )
, ,andthereisanedge from every to
3. Accept if all checks pass, otherwise, reject. 4/13/2020 CS332 ‐ Theory of Computation 16
NP is the class of languages with polynomial‐ time verifiers
Theorem: A language iff there is a polynomial‐ time verifier for
Proof:
4/13/2020 CS332 ‐ Theory of Computation 17
4/13/2020 CS332 ‐ Theory of Computation 18