PowerPoint Presentation
BU CS 332 – Theory of Computation
Lecture 21:
• Complexity Class P
• Nondeterministic time, NP
Reading:
Sipser Ch 7.2, 7.3
Mark Bun
April 12, 2021
Complexity class P
Definition: P is the class of languages decidable in
polynomial time on a basic single-tape (deterministic) TM
P = ⋃𝑘𝑘=1
∞ TIME(𝑛𝑛𝑘𝑘)
• Class doesn’t change if we substitute in another
reasonable deterministic model (Extended Church-Turing)
• Cobham-Edmonds Thesis: Roughly captures class of
problems that are feasible to solve on computers
4/12/2021 CS332 – Theory of Computation 2
Describing and analyzing polynomial-time
algorithms
• Due to Extended Church-Turing Thesis, we can still use
high-level descriptions on multi-tape machines
• Polynomial-time is robust under composition: poly(𝑛𝑛)
executions of poly(𝑛𝑛)-time subroutines run on poly(𝑛𝑛)-
size inputs gives an algorithm running in poly(𝑛𝑛) time.
⇒ Can freely use algorithms we’ve seen before as
subroutines if we’ve analyzed their runtime
• Need to be careful about size of inputs! (Assume inputs
represented in binary unless otherwise stated.)
4/12/2021 CS332 – Theory of Computation 3
Examples of languages in P
𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃 =
𝐺𝐺, 𝑠𝑠, 𝑡𝑡 𝐺𝐺 is a directed graph with a directed path from 𝑠𝑠 to 𝑡𝑡}
4/12/2021 CS332 – Theory of Computation 4
Examples of languages in P
𝐸𝐸DFA = 𝐷𝐷 𝐷𝐷 is a DFA that recognizes the empty language}
4/12/2021 CS332 – Theory of Computation 5
Examples of languages in P
• 𝑅𝑅𝐸𝐸𝑅𝑅𝑃𝑃𝑅𝑅𝑅𝑅𝑅𝑅𝐸𝐸 = 𝑥𝑥,𝑦𝑦 𝑥𝑥 and 𝑦𝑦 are relatively prime}
• 𝑃𝑃𝑅𝑅𝑅𝑅𝑅𝑅𝐸𝐸𝑃𝑃 = 𝑥𝑥 𝑥𝑥 is prime}
4/12/2021 CS332 – Theory of Computation 6
2006 Gödel Prize citation
The 2006 Gödel Prize for outstanding articles
in theoretical computer science is awarded to
Manindra Agrawal, Neeraj Kayal, and Nitin
Saxena for their paper “PRIMES is in P.”
In August 2002 one of the most ancient
computational problems was finally solved….
A polynomial-time algorithm for 𝑃𝑃𝑅𝑅𝑅𝑅𝑅𝑅𝐸𝐸𝑃𝑃?
Consider the following algorithm for 𝑃𝑃𝑅𝑅𝑅𝑅𝑅𝑅𝐸𝐸𝑃𝑃
On input 𝑥𝑥 :
For 𝑏𝑏 = 2, 3, 4, 5, … , 𝑥𝑥:
– Try to divide 𝑥𝑥 by 𝑏𝑏
– If 𝑏𝑏 divides 𝑥𝑥, accept
If all 𝑏𝑏 fail to divide 𝑥𝑥, reject
How many divisions does this algorithm require in terms of
𝑛𝑛 = | 𝑥𝑥 |? a) 𝑂𝑂 𝑛𝑛 b) 𝑂𝑂(𝑛𝑛) c) 2𝑂𝑂( 𝑛𝑛) d) 2𝑂𝑂(𝑛𝑛)
4/12/2021 CS332 – Theory of Computation 7
Beyond polynomial time
Definition: EXP is the class of languages decidable in
exponential time on a basic single-tape (deterministic) TM
EXP = ⋃𝑘𝑘=1
∞ TIME(2𝑛𝑛
𝑘𝑘
)
4/12/2021 CS332 – Theory of Computation 8
Why study P ?
Criticism of the Cobham-Edmonds Thesis:
– Algorithms running in time 𝑛𝑛100 aren’t really efficient
Response: Runtimes improve with more research
– Does not capture some physically realizable models using
randomness, quantum mechanics
Response: Randomness may not change P, useful principles
4/12/2021 CS332 – Theory of Computation 9
𝑃𝑃𝑅𝑅𝑅𝑅𝐸𝐸 𝑛𝑛 vs. 𝑃𝑃𝑅𝑅𝑅𝑅𝐸𝐸(𝑛𝑛2) 𝑃𝑃 vs. 𝐸𝐸𝐸𝐸𝑃𝑃
decidable vs.
undecidable
Nondeterministic Time
and NP
4/12/2021 CS332 – Theory of Computation 10
Nondeterministic time
Let 𝑓𝑓 ∶ ℕ → ℕ
A NTM 𝑅𝑅 runs in time 𝑓𝑓(𝑛𝑛) if on every input 𝑤𝑤 ∈ Σ𝑛𝑛,
𝑅𝑅 halts on 𝑤𝑤 within at most 𝑓𝑓(𝑛𝑛) steps on every
computational branch
4/12/2021 CS332 – Theory of Computation 11
Deterministic vs. nondeterministic time
4/12/2021 CS332 – Theory of Computation 12
Deterministic Nondeterministic
accept or reject reject
accept
𝒕𝒕(𝒏𝒏)
reject
accept
reject
Deterministic vs. nondeterministic time
4/12/2021 CS332 – Theory of Computation 13
𝑤𝑤1 𝑤𝑤2 𝑤𝑤3 𝑤𝑤4
Finite
control
𝑤𝑤1 ⊔ # 𝑤𝑤3 𝑤𝑤4
1 3 3 7
Input 𝑤𝑤 to 𝑁𝑁 (read-only)
Simulation tape (run 𝑁𝑁 on 𝑤𝑤 using
nondeterministic choices from tape 3)
Address in computation tree
Theorem: Let 𝑡𝑡 𝑛𝑛 ≥ 𝑛𝑛 be a function. Every NTM running
in time 𝑡𝑡 𝑛𝑛 has an equivalent single-tape TM running in
time 2𝑂𝑂(𝑡𝑡 𝑛𝑛 )
Proof: Simulate NTM by 3-tape TM
Counting leaves
4/12/2021 CS332 – Theory of Computation 14
What is the maximum number of leaves in a tree with
branching factor 𝑏𝑏 and depth 𝑡𝑡?
a) 𝑏𝑏𝑡𝑡
b) 𝑏𝑏𝑡𝑡
c) 𝑡𝑡𝑏𝑏
d) 2𝑡𝑡
Deterministic vs. nondeterministic time
4/12/2021 CS332 – Theory of Computation 15
Theorem: Let 𝑡𝑡 𝑛𝑛 ≥ 𝑛𝑛 be a function. Every NTM running
in time 𝑡𝑡 𝑛𝑛 has an equivalent single-tape TM running in
time 2𝑂𝑂(𝑡𝑡 𝑛𝑛 )
Proof: Simulate NTM by 3-tape TM
• # leaves:
Running time:
To simulate one root-to-leaf path:
Total time:
𝑅𝑅
input
simulation
address
Deterministic vs. nondeterministic time
4/12/2021 CS332 – Theory of Computation 16
Theorem: Let 𝑡𝑡 𝑛𝑛 ≥ 𝑛𝑛 be a function. Every NTM running
in time 𝑡𝑡 𝑛𝑛 has an equivalent single-tape TM running in
time 2𝑂𝑂(𝑡𝑡 𝑛𝑛 )
Proof: Simulate NTM by 3-tape TM in time 2𝑂𝑂(𝑡𝑡 𝑛𝑛 )
We know that a 3-tape TM can be simulated by a single-
tape TM with quadratic overhead, hence we get running
time
(2𝑂𝑂(𝑡𝑡 𝑛𝑛 ))2 = 22�𝑂𝑂(𝑡𝑡 𝑛𝑛 ) = 2𝑂𝑂(𝑡𝑡 𝑛𝑛 )
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/12/2021 CS332 – Theory of Computation 17
Nondeterministic time
Let 𝑓𝑓 ∶ ℕ → ℕ
A NTM 𝑅𝑅 runs in time 𝑓𝑓(𝑛𝑛) if on every input 𝑤𝑤 ∈ Σ𝑛𝑛,
𝑅𝑅 halts on 𝑤𝑤 within at most 𝑓𝑓(𝑛𝑛) steps on every
computational branch
NTIME(𝑓𝑓(𝑛𝑛)) is a class (i.e., set) of languages:
A language 𝑃𝑃 ∈ NTIME(𝑓𝑓(𝑛𝑛)) if there exists an NTM 𝑅𝑅
that
1) Decides 𝑃𝑃, and
2) Runs in time 𝑂𝑂(𝑓𝑓(𝑛𝑛))
4/12/2021 CS332 – Theory of Computation 18
NTIME explicitly
A language 𝑃𝑃 ∈ NTIME(𝑓𝑓(𝑛𝑛)) if there exists an NTM 𝑅𝑅
such that, on every input 𝑤𝑤 ∈ Σ∗
1. Every computational branch of 𝑅𝑅 halts in either the
accept or reject state within 𝑓𝑓( 𝑤𝑤 ) steps
2. 𝑤𝑤 ∈ 𝑃𝑃 iff there exists an accepting computational
branch of 𝑅𝑅 on input 𝑤𝑤
3. 𝑤𝑤 ∉ 𝑃𝑃 iff every computational branch of 𝑅𝑅 rejects on
input 𝑤𝑤 (or dies with no applicable transitions)
4/12/2021 CS332 – Theory of Computation 19
Complexity class NP
Definition: NP is the class of languages decidable in
polynomial time on a nondeterministic TM
NP = ⋃𝑘𝑘=1
∞ NTIME(𝑛𝑛𝑘𝑘)
Which of the following are definitely true about NP?
a) P ⊆ NP
b) NP ⊆ P
c) NP ⊈ P
d) NP ⊆ EXP
e) EXP ⊆ NP
4/12/2021 CS332 – Theory of Computation 20
Hamiltonian Path
𝑃𝑃𝑃𝑃𝑅𝑅𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃 = 𝐺𝐺, 𝑠𝑠, 𝑡𝑡 𝐺𝐺 is a directed graph and there
is a path from 𝑠𝑠 to 𝑡𝑡 that passes
through every vertex exactly once}
4/12/2021 CS332 – Theory of Computation 21
𝑠𝑠 𝑡𝑡
𝑃𝑃𝑃𝑃𝑅𝑅𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃 ∈ NP
The following nondeterministic algorithm decides
𝑃𝑃𝑃𝑃𝑅𝑅𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃 in polynomial time:
On input 𝐺𝐺, 𝑠𝑠, 𝑡𝑡 : (Vertices of 𝐺𝐺 are numbers 1, … , 𝑘𝑘)
1. Nondeterministically guess a sequence
𝑐𝑐1, 𝑐𝑐2, … , 𝑐𝑐𝑘𝑘 of numbers 1, … , 𝑘𝑘
2. Check that 𝑐𝑐1, 𝑐𝑐2, … , 𝑐𝑐𝑘𝑘 is a permutation: Every
number 1, … , 𝑘𝑘 appears exactly once
3. Check that 𝑐𝑐1 = 𝑠𝑠, 𝑐𝑐𝑘𝑘 = 𝑡𝑡, and there is an edge
from every 𝑐𝑐𝑖𝑖 to 𝑐𝑐𝑖𝑖+1
4. Accept if all checks pass, otherwise, reject.
4/12/2021 CS332 – Theory of Computation 22
Analyzing the algorithm
Need to check:
1) Correctness
2) Running time
4/12/2021 CS332 – Theory of Computation 23
An alternative characterization of NP
“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.,
𝑐𝑐 = 𝑂𝑂(|𝑤𝑤|𝑘𝑘) for some constant 𝑘𝑘)
4/12/2021 CS332 – Theory of Computation 24
𝑃𝑃𝑃𝑃𝑅𝑅𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃 has a polynomial-time verifier
Certificate 𝑐𝑐:
Verifier 𝑉𝑉:
On input 𝐺𝐺, 𝑠𝑠, 𝑡𝑡; 𝑐𝑐 : (Vertices of 𝐺𝐺 are numbers 1, … , 𝑘𝑘)
1. Check that 𝑐𝑐1, 𝑐𝑐2, … , 𝑐𝑐𝑘𝑘 is a permutation: Every
number 1, … , 𝑘𝑘 appears exactly once
2. Check that 𝑐𝑐1 = 𝑠𝑠, 𝑐𝑐𝑘𝑘 = 𝑡𝑡, and there is an edge
from every 𝑐𝑐𝑖𝑖 to 𝑐𝑐𝑖𝑖+1
3. Accept if all checks pass, otherwise, reject.
4/12/2021 CS332 – Theory of Computation 25
NP is the class of languages with polynomial-
time verifiers
Theorem: A language 𝑅𝑅 ∈ NP iff there is a polynomial-
time verifier for 𝑅𝑅
Proof:
4/12/2021 CS332 – Theory of Computation 26
4/12/2021 CS332 – Theory of Computation 27
BU CS 332 – Theory of Computation
Complexity class P
Describing and analyzing polynomial-time algorithms
Examples of languages in P
Examples of languages in P
Examples of languages in P
A polynomial-time algorithm for 𝑃𝑅𝐼𝑀𝐸𝑆?
Beyond polynomial time
Why study P ?
Nondeterministic Time and NP
Nondeterministic time
Deterministic vs. nondeterministic time
Deterministic vs. nondeterministic time
Counting leaves
Deterministic vs. nondeterministic time
Deterministic vs. nondeterministic time
Difference in time complexity
Nondeterministic time
NTIME explicitly
Complexity class NP
Hamiltonian Path
𝐻𝐴𝑀𝑃𝐴𝑇𝐻∈NP
Analyzing the algorithm
An alternative characterization of NP
𝐻𝐴𝑀𝑃𝐴𝑇𝐻 has a polynomial-time verifier
NP is the class of languages with polynomial-time verifiers
Slide Number 27