BU CS 332 – Theory of Computation
Lecture 18:
• Time Complexity
• Complexity Class P
Reading:
Sipser Ch 7.1-7.2
Mark Bun April 6, 2020
Where we are in CS 332
Automata & Formal Languages
Computability
Complexity
Previous unit: Computability theory
What kinds of problems can / can’t computers solve?
Final unit: Complexity theory
What kinds of problems can / can’t computers solve under constraints on their computational resources?
4/6/2020 CS332 – Theory of Computation 2
First topic: Time complexity
Today: Answering the basic questions
1. How do we measure complexity? (as in CS 330)
2. Asymptotic notation (as in CS 330)
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/6/2020 CS332 – Theory of Computation 3
Running time analysis
Time complexity of a TM (algorithm) = maximum number of steps it takes on a worst-case input
Formally: Let 𝑓 ∶ N → N. A TM 𝑀 runs in time 𝑓(𝑛) if on every input 𝑤 ∈ Σ∗, 𝑀 halts on 𝑤 within at most 𝑓(𝑛) steps
– Focus on worst-case running time: Upper bound of 𝑓 𝑛 must hold for all inputs of length 𝑛
– Exact running time 𝑓 𝑛 does not translate well between computational models / real computers. Instead focus on asymptotic complexity.
4/6/2020 CS332 – Theory of Computation 4
Example
How much time does it take for a basic single-tape TM to decide 𝐴 = 0𝑚1𝑚 𝑚 ≥ 0}?
Let’s analyze one particular TM 𝑀:
𝑀 = “On input 𝑤:
1. Scan input and reject if not of the form 0∗1∗ 2. While input contains both 0’s and 1’s:
Cross off one 0 and one 1
3. Accept if no 0’s and no 1’s left. Otherwise, reject.”
4/6/2020 CS332 – Theory of Computation 5
Review of asymptotic notation
𝑂-notation (upper bounds)
𝑓 𝑛 =𝑂(𝑔 𝑛 )means:
There exist constants 𝑐 > 0, 𝑛0 > 0 such that
𝑓 𝑛
≤ 𝑐𝑔 𝑛 for every 𝑛 ≥ 𝑛0
2𝑛2 = 𝑂(𝑛3) (𝑐 = 2, 𝑛0 = 0)
Example:
4/6/2020
CS332 – Theory of Computation
6
Caution: = does not mean “equals” Not reflexive:
𝑓 𝑛 =𝑂(𝑔 𝑛 )doesnotmean𝑔 𝑛 =𝑂(𝑓 𝑛 ) Example:𝑓𝑛 =2𝑛2,𝑔𝑛 =𝑛3
Alternative (better) notation: 𝑓 𝑛 ∈ 𝑂(𝑔 𝑛 )
4/6/2020 CS332 – Theory of Computation 7
Examples
• 106 𝑛3 + 2𝑛2 − 𝑛 + 10 = • 𝑛 + log𝑛 =
•𝑛(log𝑛+ 𝑛)=
•𝑛=
4/6/2020 CS332 – Theory of Computation 8
Review of asymptotic notation
Ω-notation (lower bounds)
𝑓 𝑛 =Ω(𝑔 𝑛 )means:
There exist constants 𝑐 > 0, 𝑛0 > 0 such that
𝑓 𝑛
≥ 𝑐𝑔 𝑛 for every 𝑛 ≥ 𝑛0
𝑛 = Ω(log𝑛) (𝑐 = 1, 𝑛0 = 16)
Example:
4/6/2020
CS332 – Theory of Computation
9
When should we use 𝑂 vs. Ω?
Upper bounds: Use 𝑂
“The merge-sort algorithm uses at most 𝑂(𝑛 log 𝑛)
comparisons in the worst case”
Lower bounds: Use Ω
“Every comparison-based sorting algorithm requires at
least Ω(𝑛 log 𝑛) comparisons in the worst case”
4/6/2020 CS332 – Theory of Computation 10
Review of asymptotic notation
Θ-notation (tight bounds) 𝑓 𝑛 =Θ(𝑔 𝑛 )means:
𝑓𝑛 =𝑂(𝑔𝑛) AND 𝑓𝑛 =Ω(𝑔𝑛)
Example: 1 𝑛2 − 1000𝑛 = Θ(𝑛2) 2
Generally, polynomials are easy:
𝑎𝑑𝑛𝑑 +𝑎𝑑−1𝑛𝑑−1++𝑎1𝑛+𝑎0 =(𝑛𝑑) 4/6/2020 CS332 – Theory of Computation 11
Little-oh and little-omega
𝑂-notation and -notation are like and ; 𝑜-notation and -notation are like < and >
𝑓 𝑛 =𝑜(𝑔 𝑛 )means:
For every constant 𝑐 > 0, there exists 𝑛0 > 0 such that
𝑓 𝑛
≤ 𝑐𝑔 𝑛 for every 𝑛 ≥ 𝑛0
2𝑛2 = 𝑂(𝑛3) (𝑛0 = 2/𝑐)
CS332 – Theory of Computation 12
Example:
4/6/2020
A handy-dandy chart
Notation
… means …
Think…
Example
lim 𝑓(𝑛) n←∞ 𝑔 𝑛
f(n)=O(g(n))
∃c>0,n0>0,∀n>n0 : f(n) < cg(n)
Upper bound
100n2 = O(n3)
If it exists, it is < ∞
f(n)=(g(n))
∃c>0,n0>0,∀n>n0 : cg(n) < f(n)
Lower bound
2n
= (n100)
If it exists, it is > 0
f(n)=(g(n))
both of the above: f=(g) and f = O(g)
Tight bound
log(n!)
= (n log n)
If it exists, it is > 0 and < ∞
f(n)=o(g(n))
∀c>0,∃n0>0,∀n>n0 : f(n) < cg(n)
Strict upper bound
n2 = o(2n)
Limit exists, =0
f(n)=(g(n))
∀c>0,∃n0>0,∀n>n0 : cg(n) < f(n)
Strict lower bound
n2
= (log n)
Limit exists, =∞
4/6/2020 CS332 - Theory of Computation 13
Asymptotic notation within expressions
Asymptotic notation within an expression is shorthand for an unspecified function satisfying the statement
Examples:
• 𝑛𝑂(1)
• 𝑛2 + Ω 𝑛
•1+𝑜1𝑛
4/6/2020 CS332 - Theory of Computation 14
FAABs: Frequently asked asymptotic bounds
•Polynomials.𝑎0 +𝑎1𝑛+...+𝑎𝑑𝑛𝑑 is(𝑛𝑑)if𝑎𝑑>0 • Logarithms. log 𝑎 𝑛 = (log 𝑏 𝑛) for all constants 𝑎, 𝑏 > 0
For every 𝑐 > 0, log𝑛 = 𝑜(𝑛𝑐) •Exponentials. For all 𝑏 > 1 and all 𝑑 > 0, 𝑛𝑑 = 𝑜(𝑏𝑛)
•Factorial. 𝑛!=𝑛 𝑛−1 ⋯1 By Stirling’s formula,
4/6/2020 CS332 – Theory of Computation 15
Time Complexity
4/6/2020 CS332 – Theory of Computation 16
Time complexity classes
Let𝑓∶ N→ N
TIME(𝑓(𝑛)) is a class (i.e., set) of languages:
A language 𝐴 ∈ TIME(𝑓(𝑛)) if there exists a basic single- tape (deterministic) TM 𝑀 that
1) Decides 𝐴, and
2) Runs in time 𝑂(𝑓(𝑛))
4/6/2020 CS332 – Theory of Computation 17
Example
𝐴=0𝑚1𝑚 𝑚≥0} 𝑀 = “On input 𝑤:
1. Scan input and reject if not of the form 0∗1∗ 2. While input contains both 0’s and 1’s:
Cross off one 0 and one 1
3. Accept if no 0’s and no 1’s left. Otherwise, reject.”
• 𝑀 runs in time 𝑂 𝑛2
• Is there a faster algorithm?
4/6/2020 CS332 – Theory of Computation 18
Example
𝐴=0𝑚1𝑚 𝑚≥0} 𝑀′ = “On input 𝑤:
1. Scan input and reject if not of the form 0∗1∗
2. While input contains both 0’s and 1’s:
• Reject if the total number of 0’s and 1’s remaining is odd
• Cross off every other 0 and every other 1
3. Accept if no 0’s and no 1’s left. Otherwise, reject.” • Running time of 𝑀′:
• Is there a faster algorithm?
4/6/2020 CS332 – Theory of Computation 19
Example
Running time of 𝑀′: 𝑂 𝑛 log 𝑛
Theorem (Sipser, Problem 7.49): If 𝐿 can be decided in
𝑜 𝑛 log 𝑛 time on a 1-tape TM, then 𝐿 is regular
4/6/2020 CS332 – Theory of Computation 20
Does it matter that we’re using the 1-tape model for this result?
It matters: 2-tape TMs can decide 𝐴 faster
𝑀′′ = “On input 𝑤:
1. Scan input and reject if not of the form 0∗1∗
2. Copy 0’s to tape 2
3. Scan tape 1. For each 1 read, cross of a 0 on tape 2
4. If 0’s on tape 2 finish at same time as 1’s on tape 1, accept. Otherwise, reject.”
Analysis: 𝐴 is decided in time 𝑂(𝑛) on a 2-tape TM Moral of the story (part 1): Unlike decidability, time
complexity depends on the TM model
4/6/2020 CS332 – Theory of Computation 21
How much does the model matter?
Theorem: Let 𝑡 𝑛 ≥ 𝑛 be a function. Every multi-tape TM running in time 𝑡 𝑛2 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
Moral of the story (part 2): Time complexity doesn’t depend too much on the TM model (as long as it’s deterministic, sequential)
4/6/2020 CS332 – Theory of Computation 22
Simulating Multiple Tapes
Implementation-Level Description On input 𝑤 = 𝑤 𝑤 … 𝑤
12𝑛
ሶሶ
1. Format tape into # 𝑤ሶ 𝑤 … 𝑤 # ⊔ # ⊔ # … #
12𝑛
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/6/2020 CS332 – Theory of Computation 23
How much does the model matter?
Theorem: Let 𝑡 𝑛 ≥ 𝑛 be a function. Every multi-tape TM running in time 𝑡 𝑛2 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/6/2020 CS332 – Theory of Computation 24
Extended Church-Turing Thesis
Every “reasonable” 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/6/2020 CS332 – Theory of Computation 25
Complexity Class P
4/6/2020 CS332 – Theory of Computation 26
Complexity class P
Definition: P is the class of languages decidable in
polynomial time on a basic single-tape (deterministic) TM
P = ڂ∞ TIME(𝑛𝑘) 1=𝑘
• Class doesn’t change if we substitute in another reasonable deterministic model (Extended Church-Turing)
• Cobham-Edmonds Thesis: Captures class of problems that are feasible to solve on computers
4/6/2020 CS332 – Theory of Computation 27
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 an 𝑛-vertex 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/6/2020 CS332 – Theory of Computation 28
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/6/2020 CS332 – Theory of Computation 29
Examples of languages in P • 𝑃𝐴𝑇𝐻 =
𝐺, 𝑠, 𝑡 𝐺 is a directed graph with a directed path from 𝑠 to 𝑡} • 𝐴DFA = 𝐷,𝑤 𝐷isaDFAthatacceptsinput𝑤}
• 𝑅𝐸𝐿𝑃𝑅𝐼𝑀𝐸 = • 𝑃𝑅𝐼𝑀𝐸𝑆 = 𝑥
𝑥, 𝑦 𝑥 and 𝑦 are relatively prime}
𝑥 is prime}
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….
• Every context-free language (section tomorrow)
4/6/2020 CS332 – Theory of Computation 30
𝑀 = “On input 𝑤:
1. Scan input and reject if not of the form 0∗1∗ 2. While input contains both 0’s and 1’s:
Cross off one 0 and one 1
3. Accept if no 0’s and no 1’s left. Otherwise, reject.”
4/6/2020 CS332 – Theory of Computation 31