CS21 Decidability and Tractability
Lecture 16 February 9, 2024
Complexity
• Complexity Theory = study of what is computationally feasible (or tractable) with
Copyright By PowCoder代写 加微信 powcoder
limited resources:
– running time
– storage space
– number of random bits – degree of parallelism – rounds of interaction
– others…
February 9, 2024 CS21 Lecture 16
main focus
not in this course
Worst-case analysis
• Always measure resource (e.g. running time) in the following way:
– as a function of the input length
– value of the fn. is the maximum quantity of
resource used over all inputs of given length – called “worst-case analysis”
• “input length” is the length of input string, which might encode another object with a separate notion of size
February 9, 2024 CS21 Lecture 16 3
Time complexity
Definition: the running time (“time complexity”) of a TM M is a function
steps M uses on any input of length n.
• “M runs in time f(n),” “M is a f(n) time TM” February 9, 2024 CS21 Lecture 16 4
where f(n) is the maximum number of
Time complexity
• Example: TM M deciding L = {0k1k : k ≥ 0}.
On input x:
• scan tape left-to-right, reject if 0 to right of 1
• repeat while 0’s, 1’s on tape:
• scan, crossing off one 0, one 1
• if only 0’s or only 1’s remain, reject; if neither 0’s nor 1’s remain, accept
February 9, 2024 CS21 Lecture 16
# steps? # steps?
Time complexity
• We do not care about fine distinctions – e.g. how many additional steps M takes to
check that it is at the left of tape
• We care about the behavior on large inputs
– general-purpose algorithm should be “scalable”
– overhead for e.g. initialization shouldn’t matter in big picture
February 9, 2024 CS21 Lecture 16 6
Time complexity
• Measure time complexity using asymptotic notation (“big-oh notation”)
– disregard lower-order terms in running time
– disregard coefficient on highest order term • example:
f(n) = 6n3 + 2n2 + 100n + 102781
– “f(n) is order n3” – write f(n) = O(n3)
February 9, 2024 CS21 Lecture 16 7
Asymptotic notation
Definition: given functions f,g:
say f(n) = O(g(n)) if there exist positive
integers c, n0 such that for all n ≥ n0
f(n) ≤ cg(n).
• meaning: f(n) is (asymptotically) less than or equal to g(n)
• ifg>0canassumen0 =0,bysetting c’ = max0≤n≤n0{c, f(n)/g(n)}
February 9, 2024 CS21 Lecture 16 8
Asymptotic notation facts
• “logarithmic”: O(log n)
– logb n = (log2 n)/(log2 b)
– so logbn = O(log2 n) for any constant b; therefore suppress base when write it
• “polynomial”: O(nc) = nO(1) – also: cO(log n) = O(nc’) = nO(1)
• “exponential”: O(2nδ) for δ > 0
February 9, 2024 CS21 Lecture 16 9
each bound asymptotically less than next
Time complexity
O(n) steps
≤ n repeats O(n) steps
O(n) steps
• total = O(n) + nO(n) + O(n) = O(n2)
February 9, 2024 CS21 Lecture 16 10
On input x:
• scan tape left-to-right, reject if 0 to right of 1
• repeat while 0’s, 1’s on tape:
• scan, crossing off one 0, one 1
• if only 0’s or only 1’s remain, reject; if neither 0’s nor 1’s remain, accept
Time complexity
– language is a set of strings
– a complexity class is a set of languages – complexity classes we’ve seen:
• Regular Languages, Context-Free Languages, Decidable Languages, RE Languages, co-RE languages
Definition: TIME(t(n)) = {L : there exists a TM M that decides L in time O(t(n))}
February 9, 2024 CS21 Lecture 16 11
Time complexity
• WesawthatL={0k1k:k≥0}isin TIME(n2).
• Book: it is also in TIME(n log n) by giving a more clever algorithm
• Can prove: There does not exist a (single tape) TM which decides L in time (asymptotically) less than n log n
• How about on a multitape TM?
February 9, 2024 CS21 Lecture 16 12
Time complexity
• 2-tapeTMMdecidingL={0k1k:k≥0}.
On input x:
• scan tape left-to-right, reject if 0 to right of 1
• scan 0’s on tape 1, copying them to tape 2
• scan 1’s on tape 1, crossing off 0’s on tape 2
• if all 0’s crossed off before done with 1’s reject
• if 0’s remain after done with ones, reject; otherwise accept.
February 9, 2024
CS21 Lecture 16
O(n) O(n) O(n)
total: 3*O(n) = O(n)
Multitape TMs
• Convenient to “program” multitape TMs rather than single ones
– equivalent when talking about decidability
– not equivalent when talking about time complexity
Theorem: Let t(n) satisfy t(n) ≥ n. Every multi-tape TM running in time t(n) has an equivalent TM running in time O(t(n)2).
February 9, 2024 CS21 Lecture 16 14
Multitape TMs simulation of k-tape TM by single-tape TM:
… • addnewsymbol x for each old x
• marks location of . . . “virtual heads”
(input tape)
#abab#aa#bbcd#… February 9, 2024 CS21 Lecture 16 15
abab a a bbcd
. . . . . .
• scan tape, remembering the symbols under each virtual head in the state
O(k t(n)) = O(t(n))
• make changes to reflect 1 step of M; if hit #, shift to right to make room.
O(k t(n)) = O(t(n))
Multitape TMs
Repeat: O(t(n)) times
when M halts, erase all but 1st string
#abab#aa#bbcd# …
February 9, 2024 CS21 Lecture 16 16
Multitape TMs
• Moral:feelfreetousek-tapeTMs,butbeaware of slowdown in conversion to TM
– note: if t(n) = O(nc) then t(n)2 = O(n2c )= O(nc’)
– note: if t(n) = O(2nδ) for δ > 0 then t(n)2 = O(22nδ) =
O(2nδ’) for δ’ > 0
• high-leveloperationsyouareusedtousingcan be simulated by TM with only polynomial slowdown
– e.g., copying, moving, incrementing/decrementing, arithmetic operations +, -, *, /
February 9, 2024 CS21 Lecture 16 17
Extended Church-Turing Thesis
• the belief that TMs formalize our intuitive notion of an efficient algorithm is:
• quantum computers challenge this belief February 9, 2024 CS21 Lecture 16 18
The “extended” Church-Turing Thesis
everything we can compute in time t(n) on a physical computer can be computed on a Turing Machine in time t(n)O(1) (polynomial slowdown)
Time Complexity
• interested in a coarse classification of problems. For this purpose,
– treat any polynomial running time as “efficient” or “tractable”
– treat any exponential running time as inefficient or “intractable”
Key definition: “P” or “polynomial-time” is P = ∪k ≥ 1 TIME(nk)
February 9, 2024 CS21 Lecture 16 19
Time Complexity
• Why polynomial-time?
– insensitive to particular deterministic model of
computation chosen
– closed under modular composition
– empirically: qualitative breakthrough to
achieve polynomial running time is followed by quantitative improvements from impractical (e.g. n100) to practical (e.g. n3 or n2)
February 9, 2024 CS21 Lecture 16 20
Examples of languages in P
• Recall: positive integers x, y are relatively prime if their Greatest Common Divisor (GCD) is 1.
• will show the following language is in P:
RELPRIME = {
• what is the running time of the algorithm that tries all divisors up to min{x, y}?
February 9, 2024 CS21 Lecture 16 21
Euclid’s Algorithm
• possibly earliest recorded algorithm
Example run on input <10, 22>:
x, y = 10, 22 x, y = 22, 10 x, y = 10, 2 x, y = 2, 0 reject
on input
• repeat until y = 0
• set x = x mod y
• swap x, y
• x is the GCD(x, y). If x = 1, accept; otherwise reject
February 9, 2024
CS21 Lecture 16
Euclid’s Algorithm
• possibly earliest recorded algorithm
Example run on input <24, 5>:
x, y = 24, 5 x, y = 5, 4 x, y = 4, 1 x, y = 1, 0 accept
on input
• repeat until y = 0
• set x = x mod y
• swap x, y
• x is the GCD(x, y). If x = 1, accept; otherwise reject
February 9, 2024
CS21 Lecture 16
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com