Introduction to Complexity Theory Spring 2024 with William Hoza

CMSC 28100 Introduction to Complexity Theory Complexity Theory Spring 2024 Instructor: William Hoza 1

Problem set 1 Problem set 1 is available in Canvas If you aren t officially enrolled in the course, send me an email. I ll add you to Canvas so you can access the homework Office hours (Thursday, Friday, Monday) are a good place to find study partners / homework collaborators 2

Which problems Which problems can be solved can be solved through computation? through computation? 3

Turing machines In each step, the machine decides What to write Which direction to move the head (left or right) The new state The decision is based only on the current state and the observed symbol 4

Defining Turing machines rigorously Def: A Turing machine is a 9-tuple ? = (?, , , , ,?,?0,?accept,?reject) such that ?is a finite set (the set of states ) and are alphabets (the input alphabet and the tape alphabet ) We have { , } and , Warning: The definition ? is a function ?:? ? {L,R}(the transition function ) in the textbook is slightly If ? ?, = (? ,? ,?), then ? = and ? = R different. Sorry! (The two models are equivalent.) If ? ?,? = ? ,? ,? and ? , then ? ?0,?accept,?reject ? and ?accept ?reject. 5

0,1 R State diagram L ?0 0 R Each node represents a state ?reject ?0 0,1 L An arc from ? to ? L ?1 1 labeled ? ? ,? ?accept means ? ?,? = (? ,?,?) 0,1 R The label ? ? is shorthand for ? ?,? An arc labeled ?,? represents two arcs ( ? and ? ) 6

Defining TM computation rigorously The transition function ? describes the local evolution of the computation Now let s precisely describe the global evolution of the computation 7

Configurations of a Turing machine Let ? = (?, , , , ,?,?0,?accept,?reject) be a Turing machine A configuration of ? is a triple (?,?,?) where ? , ? ?, and ? . Interpretation: The tape currently contains ?? The machine is currently in state ? and the head is currently located in cell ? + 1 ?2 ?3 ?1 ?? ?2 ?? ?1 ? 8

Configuration shorthand Instead of ?,?,? , we often write ??? We think of ??? as a string over the alphabet ? This shorthand can only be used if ? = , which we can assume without loss of generality by renaming states if necessary 9

Equivalent configurations Note: ??? and ??? are technically two distinct configurations However, they represent the exact same scenario We can say that they are equivalent (A configuration is a finite string, even though the tape is infinitely long) 10

The initial configuration Let ? be an input The initial configuration of ? on ? is ?0? 11

The next configuration Let ??? be any configuration of ? such that ?? begins with We define NEXT ??? as follows: Break ??? into individual symbols: ??? = ?1?2 ?? 1????1?2?3 ?? Let ? be the symbol that ?is currently observing ? = ?1, unless ? = 0, in which case ? = If ? ?,? = ? ,? ,R , then NEXT ??? = ?1?2 ?? 1??? ? ?2?3 ?? If ? ?,? = ? ,? ,L , then NEXT ??? = ?1?2 ?? 1? ??? ?2?3 ?? This is well-defined (? ?), because ? must move right if ? = 12

Halting configurations An accepting configuration is a configuration of the form ??accept? A rejecting configuration is a configuration of the form ??reject? A halting configuration is an accepting or rejecting configuration 13

Computation history Let ? be an input Let ?0 be the initial configuration of ? on ?, i.e., ?0= ?0? Inductively, for each ? , let ??+1= NEXT ?? The computation history of ? on ? is the sequence ?0,?1, ,??, where ?? is the first halting configuration in the sequence If there is no such ??, then the computation history is ?0,?1,?2, (infinite) 14

Accepting, rejecting, and looping If the computation history of ? on ? ends with an accepting configuration, then we say that ? accepts ? If the computation history of ? on ? ends with a rejecting configuration, then we say that ? rejects ? In either of those cases, we say that ? halts on ?. If the computation history of ? on ? is infinite, then we say that ? loops on ? 15

Time Suppose the computation history of ? on ? is ?0,?1, ,?? We say that ? is the running time of ? on ? If ? loops on ?, then its running time on ? is We say that ? halts on ? within ? steps if the running time of ? on ? is at most ? 16

Which of the following statements is false? Space B: If ? halts on ? within |?| steps, then ? halts on ?? A: Space used running time + 2 C: If ? halts on ?, then ? uses a finite amount of space on ? D: If ? uses a finite amount of space on ?, then ? halts on ? Let ?0,?1, be the (finite or infinite) computation history of ? on ? Respond at PollEv.com/whoza or text whoza to 22333 Write ??= ??,??,?? where ?? , ?? ?, ?? The space used by ? on ? is max ??+ 1, i.e., it s the maximum ? such ? that during the computation of ? on ?, the head visits cell ? (Can be ) 17