PowerPoint Presentation
BU CS 332 – Theory of Computation
Lecture 20:
• Time/Space Hierarchies
• Complexity Class P
Reading:
Sipser Ch 9.1, 7.2
Mark Bun
April 7, 2021
Last Time
• Asymptotic notation
• Analyzing time / space usage of Turing machines
(algorithms)
• Multi-tape TMs can solve problems faster than single-
tape TMs
4/7/2021 CS332 – Theory of Computation 2
Time complexity
Time complexity of a TM (algorithm) = maximum number of
steps it takes on a worst-case input
Formally: Let 𝑓𝑓 ∶ ℕ → ℕ. A TM 𝑀𝑀 runs in time 𝑓𝑓(𝑛𝑛) if on
every input 𝑤𝑤 ∈ Σ𝑛𝑛, 𝑀𝑀 halts on 𝑤𝑤 within at most 𝑓𝑓(𝑛𝑛) steps
A language 𝐴𝐴 ∈ TIME(𝑓𝑓(𝑛𝑛)) if there exists a basic single-tape
(deterministic) TM 𝑀𝑀 that
1) Decides 𝐴𝐴, and
2) Runs in time 𝑂𝑂(𝑓𝑓(𝑛𝑛))
4/7/2021 CS332 – Theory of Computation 3
Single vs. Multi-Tape
Theorem: Let 𝑡𝑡 𝑛𝑛 ≥ 𝑛𝑛 be a function. Every multi-tape
TM running in time 𝑡𝑡 𝑛𝑛 has an equivalent single-tape TM
running in time 𝑂𝑂(𝑡𝑡 𝑛𝑛 2)
Proof idea:
We already saw how to simulate a multi-tape TM with a
single-tape TM
Need a runtime analysis of this construction
4/7/2021 CS332 – Theory of Computation 4
Applying the simulation theorem
Suppose 𝐵𝐵 is decidable in time 𝑂𝑂(𝑛𝑛2) on a 42-tape TM.
Then a basic single-tape TM can decide 𝐵𝐵 in time…
a) 𝑂𝑂 𝑛𝑛2
b) 𝑂𝑂(𝑛𝑛4)
c) 𝑂𝑂 𝑛𝑛84
d) 2𝑂𝑂(𝑛𝑛)
4/7/2021 CS332 – Theory of Computation 5
Simulating Multiple Tapes
(Implementation-Level Description)
On input 𝑤𝑤 = 𝑤𝑤1𝑤𝑤2 …𝑤𝑤𝑛𝑛
1. Format tape into # �̇�𝑤1𝑤𝑤2 …𝑤𝑤𝑛𝑛# ⊔̇ # ⊔̇ # … #
2. For each move of 𝑀𝑀:
Scan left-to-right, finding current symbols
Scan left-to-right, writing new symbols,
Scan left-to-right, moving each tape head
If a tape head goes off the right end, insert blank
If a tape head goes off left end, move back right
4/7/2021 CS332 – Theory of Computation 6
Single vs. Multi-Tape
Theorem: Let 𝑡𝑡 𝑛𝑛 ≥ 𝑛𝑛 be a function. Every multi-tape
TM running in time 𝑡𝑡 𝑛𝑛 has an equivalent single-tape TM
running in time 𝑂𝑂(𝑡𝑡 𝑛𝑛 2)
Proof: Time analysis of simulation
• Time to initialize (i.e., format tape): 𝑂𝑂 𝑛𝑛 + 𝑘𝑘
• Time to simulate one step of multi-tape TM: 𝑂𝑂 𝑘𝑘 ⋅ 𝑡𝑡 𝑛𝑛
• Number of steps to simulate: 𝑡𝑡 𝑛𝑛
⇒ Total time:
4/7/2021 CS332 – Theory of Computation 7
Extended Church-Turing Thesis
Every “reasonable” (physically realizable) model of
computation can be simulated by a basic, single-tape TM
with only a polynomial slowdown.
E.g., doubly infinite TMs, multi-tape TMs, RAM TMs
Does not include nondeterministic TMs (not reasonable)
Possible counterexamples? Randomized computation,
parallel computation, DNA computing, quantum
computation
4/7/2021 CS332 – Theory of Computation 8
Space complexity
Space complexity of a TM (algorithm) = maximum number of
tape cells it uses on a worst-case input
Formally: Let 𝑓𝑓 ∶ ℕ → ℕ. A TM 𝑀𝑀 runs in space 𝑓𝑓(𝑛𝑛) if on
every input 𝑤𝑤 ∈ Σ𝑛𝑛, 𝑀𝑀 halts on 𝑤𝑤 using at most 𝑓𝑓(𝑛𝑛) cells
A language 𝐴𝐴 ∈ SPACE(𝑓𝑓(𝑛𝑛)) if there exists a basic single-
tape (deterministic) TM 𝑀𝑀 that
1) Decides 𝐴𝐴, and
2) Runs in time 𝑂𝑂(𝑓𝑓(𝑛𝑛))
4/7/2021 CS332 – Theory of Computation 9
How does space relate to time?
Which of the following is true for every function
𝑓𝑓 𝑛𝑛 ≥ 𝑛𝑛?
a) 𝑇𝑇𝑇𝑇𝑀𝑀𝑇𝑇 𝑓𝑓 𝑛𝑛 ⊆ 𝑆𝑆𝑆𝑆𝐴𝐴𝑆𝑆𝑇𝑇(𝑓𝑓 𝑛𝑛 )
b) 𝑆𝑆𝑆𝑆𝐴𝐴𝑆𝑆𝑇𝑇 𝑓𝑓 𝑛𝑛 ⊆ 𝑇𝑇𝑇𝑇𝑀𝑀𝑇𝑇(𝑓𝑓 𝑛𝑛 )
c) 𝑇𝑇𝑇𝑇𝑀𝑀𝑇𝑇 𝑓𝑓 𝑛𝑛 = 𝑆𝑆𝑆𝑆𝐴𝐴𝑆𝑆𝑇𝑇(𝑓𝑓 𝑛𝑛 )
d) None of the above
4/7/2021 CS332 – Theory of Computation 10
Back to our examples
𝐴𝐴 = 0𝑚𝑚1𝑚𝑚 𝑚𝑚 ≥ 0}
Theorem: Let 𝑠𝑠 𝑛𝑛 ≥ 𝑛𝑛 be a function. Every multi-tape
TM running in time 𝑠𝑠 𝑛𝑛 has an equivalent single-tape TM
running in time 𝑂𝑂(𝑠𝑠(𝑛𝑛))
4/7/2021 CS332 – Theory of Computation 11
Hierarchy Theorems
4/7/2021 CS332 – Theory of Computation 12
More time, more problems
We know, e.g., that 𝑇𝑇𝑇𝑇𝑀𝑀𝑇𝑇 𝑛𝑛2 ⊆ 𝑇𝑇𝑇𝑇𝑀𝑀𝑇𝑇(𝑛𝑛3)
(Anything we can do in quadratic time we can do in cubic time)
Question: Are there problems that we can solve in cubic time
that we cannot solve in quadratic time?
Theorem: There is a language 𝐿𝐿 ∈ 𝑇𝑇𝑇𝑇𝑀𝑀𝑇𝑇 𝑛𝑛3 ,
but 𝐿𝐿 ∉ 𝑇𝑇𝑇𝑇𝑀𝑀𝑇𝑇(𝑛𝑛2)
4/7/2021 CS332 – Theory of Computation 13
“Time hierarchy”:
𝑇𝑇𝑇𝑇𝑀𝑀𝑇𝑇 𝑛𝑛 𝑇𝑇𝑇𝑇𝑀𝑀𝑇𝑇 𝑛𝑛2 𝑇𝑇𝑇𝑇𝑀𝑀𝑇𝑇 𝑛𝑛3 𝑇𝑇𝑇𝑇𝑀𝑀𝑇𝑇 𝑛𝑛4 …
Diagonalization redux
4/7/2021 CS332 – Theory of Computation 14
TM 𝑀𝑀 𝑀𝑀( 𝑀𝑀1 )? 𝑀𝑀( 𝑀𝑀2 )? 𝑀𝑀( 𝑀𝑀3 )? 𝑀𝑀( 𝑀𝑀4 )?
𝑀𝑀1 Y N Y Y
𝑀𝑀2 N N Y Y
𝑀𝑀3 Y Y Y N
𝑀𝑀4 N N Y N
…
…
𝑈𝑈𝑈𝑈 = 𝑀𝑀 𝑀𝑀 is a TM that does not accept input 𝑀𝑀 }
𝐿𝐿 = 𝑀𝑀 𝑀𝑀 is a TM that does not accept input 𝑀𝑀
within 𝑛𝑛2.5 steps}
𝑈𝑈( 𝑈𝑈 )?
𝑈𝑈
An explicit separating language
Theorem: 𝐿𝐿 = 𝑀𝑀 𝑀𝑀 is a TM that does not accept
input 𝑀𝑀 within 𝑛𝑛2.5 steps}
is in 𝑇𝑇𝑇𝑇𝑀𝑀𝑇𝑇(𝑛𝑛3), but not in 𝑇𝑇𝑇𝑇𝑀𝑀𝑇𝑇(𝑛𝑛2)
Proof: In 𝑇𝑇𝑇𝑇𝑀𝑀𝑇𝑇(𝑛𝑛3)
On input 𝑀𝑀 :
1. Simulate 𝑀𝑀 on input 𝑀𝑀 for 𝑛𝑛2.5 steps
2. If 𝑀𝑀 accepts, reject. If 𝑀𝑀 rejects or did not yet
halt, accept.
4/7/2021 CS332 – Theory of Computation 15
An explicit separating language
Theorem: 𝐿𝐿 = 𝑀𝑀 𝑀𝑀 is a TM that does not accept
input 𝑀𝑀 within 𝑛𝑛2.5 steps}
is in 𝑇𝑇𝑇𝑇𝑀𝑀𝑇𝑇(𝑛𝑛3), but not in 𝑇𝑇𝑇𝑇𝑀𝑀𝑇𝑇(𝑛𝑛2)
Proof: Not in 𝑇𝑇𝑇𝑇𝑀𝑀𝑇𝑇(𝑛𝑛2)
Suppose for contradiction that 𝑈𝑈 decides 𝐿𝐿 in time 𝑂𝑂(𝑛𝑛2)
4/7/2021 CS332 – Theory of Computation 16
Time and space hierarchy theorems
• For any* function 𝑡𝑡 𝑛𝑛 ≥ 𝑛𝑛 log𝑛𝑛 , a language exists that is
decidable in 𝑡𝑡(𝑛𝑛) time, but not in 𝑜𝑜 𝑡𝑡 𝑛𝑛
log 𝑡𝑡 𝑛𝑛
time.
• For any* function 𝑠𝑠 𝑛𝑛 ≥ log𝑛𝑛 , a language exists that is
decidable in 𝑠𝑠(𝑛𝑛) space, but not in 𝑜𝑜 𝑠𝑠(𝑛𝑛) space.
*“time constructible” and “space constructible”, respectively
4/7/2021 CS332 – Theory of Computation 17
Complexity Class P
4/7/2021 CS332 – Theory of Computation 18
Time and space complexity
The basic questions
1. How do we measure complexity?
2. Asymptotic notation
3. How robust is the TM model when we care about
measuring complexity?
4. How do we mathematically capture our intuitive
notion of “efficient algorithms”?
4/7/2021 CS332 – Theory of Computation 19
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/7/2021 CS332 – Theory of Computation 20
Check your type checker: P
Consider the following computational problem: Given two
numbers 𝑥𝑥,𝑦𝑦 (written in binary), output their sum
𝑥𝑥 + 𝑦𝑦 (in binary). Which of the following is true?
a) This is a problem in P
b) This problem is not in P because it cannot be solved
by a Turing machine (i.e., it’s undecidable)
c) This problem is not in P because it cannot be solved in
polynomial time
d) This problem is not in P because it is not a decision
problem (i.e., a language)
4/7/2021 CS332 – Theory of Computation 21
A note about encodings
We’ll still use the notation for “any reasonable”
encoding of the input to a TM…but now we have to be
more careful about what we mean by “reasonable”
How long is the encoding of a 𝑉𝑉-vertex, 𝑇𝑇-edge graph…
… as an adjacency matrix?
… as an adjacency list?
How long is the encoding of a natural number 𝑘𝑘
… in binary?
… in decimal?
… in unary?
4/7/2021 CS332 – Theory of Computation 22
When the encoding matters
The “same” algorithm can have wildly different runtimes
depending on how the input is encoded!
𝑀𝑀 = “On input 𝑥𝑥 (a natural number encoded in binary):
1. List the binary numbers 1, 2, … , 𝑥𝑥 and accept.”
𝑀𝑀′ = “On input 𝑥𝑥 (a natural number encoded in unary):
1. List the binary numbers 1, 2, … , 𝑥𝑥 and accept.”
4/7/2021 CS332 – Theory of Computation 23
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/7/2021 CS332 – Theory of Computation 24
Examples of languages in P
𝑆𝑆𝐴𝐴𝑇𝑇𝑃𝑃 =
𝐺𝐺, 𝑠𝑠, 𝑡𝑡 𝐺𝐺 is a directed graph with a directed path from 𝑠𝑠 to 𝑡𝑡}
4/7/2021 CS332 – Theory of Computation 25
Examples of languages in P
𝑇𝑇DFA = 𝑈𝑈 𝑈𝑈 is a DFA that recognizes the empty language}
4/7/2021 CS332 – Theory of Computation 26
Examples of languages in P
• 𝑅𝑅𝑇𝑇𝐿𝐿𝑆𝑆𝑅𝑅𝑇𝑇𝑀𝑀𝑇𝑇 = 𝑥𝑥,𝑦𝑦 𝑥𝑥 and 𝑦𝑦 are relatively prime}
• 𝑆𝑆𝑅𝑅𝑇𝑇𝑀𝑀𝑇𝑇𝑆𝑆 = 𝑥𝑥 𝑥𝑥 is prime}
4/7/2021 CS332 – Theory of Computation 27
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/7/2021 CS332 – Theory of Computation 28
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/7/2021 CS332 – Theory of Computation 29
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/7/2021 CS332 – Theory of Computation 30
𝑇𝑇𝑇𝑇𝑀𝑀𝑇𝑇 𝑛𝑛 vs. 𝑇𝑇𝑇𝑇𝑀𝑀𝑇𝑇(𝑛𝑛2) 𝑆𝑆 vs. 𝑇𝑇𝐸𝐸𝑆𝑆
decidable vs.
undecidable
BU CS 332 – Theory of Computation
Last Time
Time complexity
Single vs. Multi-Tape
Applying the simulation theorem
Simulating Multiple Tapes
Single vs. Multi-Tape
Extended Church-Turing Thesis
Space complexity
How does space relate to time?
Back to our examples
Hierarchy Theorems
More time, more problems
Diagonalization redux
An explicit separating language
An explicit separating language
Time and space hierarchy theorems
Complexity Class P
Time and space complexity
Complexity class P
Check your type checker: P
A note about encodings
When the encoding matters
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 ?