CSE 105 THEORY OF COMPUTATION Spring 2019 https://cseweb.ucsd.edu/classes/sp19/cse105-a/ Today's learning goals Sipser Ch 5.1, 7 (highlights) Construct reductions from one problem to another. Distinguish between computability and complexity Section 7.1: time complexity, asymptotic upper bounds. Section 7.2: polynomial time, P Section 7.3: NP, polynomial verifiers, nondeterministic

machines. Today's learning goals Sipser Ch 5.1, 7 (highlights) Specifically for complexity theory: Define the time complexity class P and name some problems in P Distinguish between polynomial and exponential DTIME Define the class NP and name some problems in NP State and explain P=NP? Define NP-completeness and connect it to P=NP Describe how reductions are used both for questions

of decidability and of complexity. So far Decidable Undecidable ADFA ATM EDFA

ETM EQDFA EQTM INFINITEDFA INFINITETM RevDFA REGULARTM

STM RecTM Give algorithm! Which of the following is not closed under complementation? A. The set of decidable languages B. The set of undecidable languages C. The set of recognizable

languages D. More than one of the above E. None of the above. Diagonalization or Reduction Reducing sets to one another We saw ATM reduces to HALTTM Given genie G deciding HALTTM, construct solution for ATM: "On input : 1. Run G on . If rejects, reject.

2. If accepts, run M on w. If accepts, accept; if rejects; reject." What about in the other direction? Reducing sets to one another Given genie GATM deciding ATM, construct solution for HALTTM: "On input : Not just decidable For a given algorithm working on a given input, how long do we need to wait for an answer? How does the running time depend on the input in the worst-case? averagecase? Expect to have to spend more time on larger inputs.

What's in common among all problems that are efficiently solvable? Measuring time For a given algorithm working on a given input, how long do we need to wait for an answer? Count steps! How does the running time depend on the input in the worstcase? average-case? Big-O What's in common among all problems that are efficiently solvable? Time(n) Time complexity

For M a deterministic decider, its running time or time complexity is the function f: N R+ given by f(n) = maximum number of steps M takes before halting, over all inputs of length n. worst-case analysis Time complexity For M a deterministic decider, its running time or time complexity is the function f: N R+ given by f(n) = maximum number of steps M takes before halting, over all inputs of length n.

Instead of calculating precisely, estimate f(n) by using big-O notation. Time complexity classes TIME(t(n)) = { L | L is decidable by a TM running in O(t(n)) } Exponential Polynomial Logarithm Why is it okay to group all polynomial running times? Contains all the "feasibly solvable" problems. Invariant for all the "usual" deterministic TM models multitape machines (Theorem 7.8)

multi-write Working with P Problems encoded by languages of strings Need to make sure coding/decoding of objects can be done in polynomial time. Algorithms can be described in high-level or implementation level CAUTION: not allowed to guess / make non-deterministic moves. Time complexity classes TIME(t(n)) = { L | L is decidable by a TM running in O(t(n)) }

Exponential Brute-force search Polynomial Invariant under many models of TMs Logarithmic May not need to read all of input Which machine model?

q0 q0 nondeterministic computation deterministic computation qacc qrej qrej

qrej qacc Time complexity For M a deterministic decider, its running time or time complexity is the function f: N R+ given by f(n) = maximum number of steps M takes before halting, over all inputs of length n. For M a nondeterministic decider, its running time or time complexity is the function f: N R+ given by f(n) = maximum number of steps M takes before halting on any branch of its computation, over all inputs of length n.

Time complexity classes DTIME ( t(n) ) = { L | L is decidable by O( t(n) ) deterministic, single-tape TM } NTIME ( t(n) ) = { L | L is decidable by O( t(n) ) nondeterministic, single-tape TM } Which of the following is (known to be) not true? A. DTIME(n22) is a subset of DTIME(n33) B. DTIME(n22) is a subset of NTIME(n22) C. NTIME(n22) a subset of DTIME(n22) D. More than one of the above E. None of the above "Feasible" i.e. P

Can't use nondeterminism Can use multiple tapes Often need to be "more clever" than nave / brute force approach Examples PATH = { | G is digraph with n nodes there is path from s to t} RELPRIME = { | x and y are relatively prime integers} Use Euclidean Algorithm to show in P L(G) = {w | w is generated by G} where G is any CFG Use Dynamic Programming to show in P "Verifiable" i.e. NP Best known solution is brute-force Look for some "certificate" if had one, could quickly check if it

works P = NP? P vs. NP Problems in P Problems in NP (Membership in any) CFL Any problem in P

PATH HAMPATH EDFA CLIQUE EQDFA VERTEX-COVER Addition, multiplication of integers

TSP SAT Decidable NP? P CF Regular

Reductions to the rescue Sipser p. 271,276 1970s Stephen Cook and Leonid Levin indepdendently and in parallel lay foundations of NP-completeness Intuitively: if an NP-complete problem has a polynomial algorithm, then all NP problems are polynomail time solvable. A language B is NP-complete if it is in NP and every A in NP is polynomial-time reducible to it. Cook-Levin Theorem: SAT is NP-complete. What would prove that P = NP? A. Showing that a problem Sipser

solvable by brute-force p. 271,276 methods has a nondeterministic solution. B. Showing thatindepdendently there are two distinct 1970s Stephen Cook and Leonid Levin andNPin complete problems. parallel lay foundations of NP-completeness C. Finding a polynomial time solution for an NPcomplete problem. Intuitively: if an NP-complete

has polynomialproblem algorithm, D. problem Proving that anaNP-complete is not solvable time in polynomial time. then all NP problems are polynomail solvable. E. I don't know

Reductions to the rescue A language B is NP-complete if it is in NP and every A in NP is polynomial-time reducible to it. Cook-Levin Theorem: SAT is NP-complete.