CS 332Intro to Theory of Computation LECTURE 21 CS 332 Last time Recursion theorem Measuring complexity Asymptotic notation Today Measuring complexity Relationship between models Class P Sofya Raskhodnikova 3/17/2016

CS 332 Exercise In the future we will find algorithms for all computational problems, that is, problems with well-defined inputs and desired outputs. A. True. I am an optimist. B. It is difficult to make predictions, especially about the future. (K.K. Steincke) C. False. Finitely many people will be able to design only finitely many algorithms. D. False. There are more computational problems than algorithms. 3/17/2016 L22.2 CS 332

Predictions It is not hard to make predictions, it is hard to make interesting predictions (of unpredictable events you dont control). It will be dark tonight at 11pm. Most people in this room will have another meal today. The exercise from the previous slide will appear on the final. 02/07/2020 L22.3 CS 332 Running time analysis If M is a TM and then

M runs in time means for every input of length , M on halts within steps Focus on worst case: upper bound on running time for all inputs of given length Exact time depends on computer instead measure asymptotic growth 02/07/2020 S. Raskhodnikova; based on slides by E. Demaine, C. Leiserson L21.4 CS 332 Time complexity classes TIME() is a class of languages. TIME() means that some 1-tape TM M

that runs in time O() decides A. 02/07/2020 L21.5 CS 332 How much time/memory needed to decide a language? Example: Consider = 1. Scan input and reject if it is not of the form 2. Repeat while both 0s and 1s remain on the tape: 3. Cross off one 0 and one 1 4. Accept if no 0s and no 1s left; otherwise reject.

runs in time Is there a faster algorithm? 02/07/2020 L21.6 CS 332 How much time/memory needed to decide a language? Example: Consider = 1. Scan input and reject if it is not of the form 2. Repeat while both 0s and 1s remain on the tape: 3. Reject if total number of 0s and 1s remaining is odd.

4. Cross off every other 0 starting from the first 0 and every other 1 starting from the first 1 runs in5.time Accept so if no 0s and no 1s left; otherwise reject. Sipser, Problem 7.49: If language L can be decided in o time on a 1-tape TM then L is regular. 1-tape TM need time to decide A. 02/07/2020 L21.7 CS 332 Two-tape TM can do it faster Example: Consider

FINITE CONTROL = 1. 2. 3. 4. 0 0 .. 0 1 1 .. 1 Scan input and reject if it is not of the form Copy 0s on tape 2. Scan tape 1. For each 1 read, cross off a 0 on tape 2. Accept if no 0s remain on tape 2; otherwise reject. A is decided in time (linear time) on a 2-tape TM. Unlike decidability,

the complexity of the language depends on the model. 02/07/2020 L21.8 CS 332 Complexity relationships between models: number of tapes Theorem. Let be a function, where Every time multitape TM has an equivalent time 1-tape TM. Proof: Recall: we already showed how to simulate multitape TMs by 1-tape TMs. Need time analysis of the simulation. 02/07/2020

L21.9 Theorem: Every Multitape Turing Machine can be transformed into a single-tape Turing Machine 1 0 0 # 0 FINITE STATE CONTROL FINITE STATE CONTROL

1 0 # # SIMULATING MULTIPLE TAPES 100 00 ###R L#100###R L#100# L#100# 1 #R

qqijjRSS qi1 qi1 qi1qj101RSS 1. Format tape. 2. For each move of the k-tape TM: Scan left-to-right, finding current symbols Scan left-to-right, writing new symbols Scan left-to-right, moving each tape head. 3. If a tape head goes off right end, insert blank. If tape head goes off left end, move back right. CS 332 Complexity relationships between models: number of tapes Theorem. Let be a function, where Every time multitape TM has

an equivalent time 1-tape TM. Proof: Time analysis of the simulation. Time initialize tape: Time to simulate one step of the multitape TM: (at any point nonblank squares on each tape) Number of steps to simulate: Total time: 02/07/2020 L21.12 CS 332 Exercise Let be a function, where Every 3-tape TM that runs in time O() can be simulated by a 1-tape TM that runs in time A. B.

C. D. E. 3/17/2016 O() O() O() O Some 3-tape TMs cant be simulated by 1-tape TMs L22.13 CS 332 The class P P is the class of languages decidable in polynomial time on a deterministic 1-tape TM:

The same class even if we substitute another reasonable deterministic model. Roughly the class of problems realistically solvable on a computer. 02/07/2020 L21.14 CS 332 Time complexity of NTMs The running time a nondeterministic decider is if on all inputs of length , NTMtakes at most steps on the longest nondeterministic branch. 02/07/2020 L23.16

CS 332 Time complexity of NTMs Deterministic Nondeterministic () accept accept or reject reject Length of the longest computational branch, even if accepts before 02/07/2020 L23.17

CS 332 Complexity relationships between models: nondeterminism Theorem. Let be a function, where Every time nondeterministic TM has an equivalent time 1-tape deterministic TM. Proof: Simulate an NTM by a 3-tape TM. # of leaves # of nodes M Time increment the address and simulate from the root to a node: Total: = 02/07/2020 input

simulation address accept () reject L22.18 CS 332 Complexity relationships between models: nondeterminism Theorem. Let be a function, where Every time nondeterministic TM has

an equivalent time 1-tape deterministic TM. Proof: So, a 3-tape TM can simulate an NTM in time. Converting to a 1-tape TM at most squares the running time: 02/07/2020 L22.19 CS 332 Difference in time complexity At most polynomial difference between all reasonable deterministic models. At most exponential difference between deterministic and nondeterministic models. 02/07/2020 L3.20

CS 332 The class P P is the class of languages decidable in polynomial time on a deterministic 1-tape TM: The same class even if we substitute another reasonable deterministic model. Roughly the class of problems realistically solvable on a computer. 02/07/2020 L23.21 CS 332 Examples of languages in P

PATH ={ is a directed graph that has a directed path from to } RELPRIME = { and are relatively prime} PRIMES ={ is a prime number} [2002] Every context-free language (On the board) 02/07/2020 L22.22 CS 332 Recall: Chomsky Normal Form for CFGs Can have a rule . All remaining rules are of the form

Cannot have on the RHS of any rule. Lemma. Any CFG can be converted into an equivalent CFG in Chomsky normal form. Lemma. If G is in Chomsky normal form, any derivation of string w of length in G has steps. 02/07/2020 Sofya Raskhodnikova; based on slides by Nick Hopper L22.23 CS 332 A decider for a CFL Let L be a CFL generated by a CFG G in CNF M = `` On input , where is a string: 1. Let . 2. Test all derivations with steps. 3. Accept if any derived . O.w. reject.

How long does it take? Idea: use dynamic programming (exponential time) (on the board) Solve smaller subproblems Record results in a table Construct solution for each subproblem from smaller solved instances 02/07/2020 L22.24