Microsoft PowerPoint – CS332-Lec20-ann
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 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
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 on a 42‐tape TM.
Then a basic single‐tape TM can decide in time…
a)
b)
c)
d)
4/7/2021 CS332 ‐ Theory of Computation 5
Simulating Multiple Tapes
(Implementation‐Level Description)
On input
1. Format tape into
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
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 if there exists a basic single‐
tape (deterministic) TM that
1) Decides , and
2) Runs in space
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
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
(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 ,
but
4/7/2021 CS332 ‐ Theory of Computation 13
“Time hierarchy”:
Diagonalization redux
4/7/2021 CS332 ‐ Theory of Computation 14
TM 𝑀 𝑀 𝑀 ? 𝑀 𝑀 ? 𝑀 𝑀 ? 𝑀 𝑀 ?
𝑀 Y N Y Y
𝑀 N N Y Y
𝑀 Y Y Y N
𝑀 N N Y N
…
…
.
𝐷 𝐷 ?
𝐷
An explicit separating language
Theorem:
.
is in , but not in
Proof: In
On input :
1. Simulate on input for . 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 in , but not in
Proof: Not in
Suppose for contradiction that decides in time
4/7/2021 CS332 ‐ Theory of Computation 16
Time and space hierarchy theorems
• For any* function a language exists that is
decidable in time, but not in time.
• For any* function 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
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
Definition: is the class of languages decidable in
polynomial time on a basic single‐tape (deterministic) TM
• 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:
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
b) This problem is not in because it cannot be solved
by a Turing machine (i.e., it’s undecidable)
c) This problem is not in because it cannot be solved in
polynomial time
d) This problem is not in 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 and accept.”
“On input (a natural number encoded in unary):
1. List the binary numbers and accept.”
4/7/2021 CS332 ‐ Theory of Computation 23