CSE 105 Theory of Computation

CSE 105 Theory of Computation

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.

Recently Viewed Presentations

  • MS Society of Association Executives September 19, 2018

    MS Society of Association Executives September 19, 2018

    the "commonality of interest standard" so that associations can be composed of members who are in the same trade, industry, line of business, or who have a principal place of business within the same state or metropolitan area; and ......
  • Legal Issues Arising from the Use of Mobile Devices in ...

    Legal Issues Arising from the Use of Mobile Devices in ...

    Ⅰ. Introduction. Ⅱ. Development of Mobile Finance. Ⅲ. Legal Issues Arising from Mobile Finance. Ⅳ. Conclusion. Legal Issues Arising from the Use of Mobile Devices in Electronic Commerce
  • The Renaissance Questions of the Day

    The Renaissance Questions of the Day

    The Renaissance Questions of the Day Daniel W. Blackmon AP European History Coral Gables Sr. High
  • REVIEW VII THE FORBIDDEN CITY Located in modern-day

    REVIEW VII THE FORBIDDEN CITY Located in modern-day

    Beginning in the early 1600s, Mogul emperors granted concessions to allow the British to trade in India. Trading posts were set up along the coast in places such as Madras and Bombay. The British East India Company established forts to...
  • Intersection Design Fundamentals - ICMM

    Intersection Design Fundamentals - ICMM

    This however is conundrum that leads to a false sense of increased visibility, where in fact in most circumstances it orientates the A pillar subtended angle of the cab along the primary road way severely reducing visibility over a longer...
  • Pooria Kamran Rashani

    Pooria Kamran Rashani

    I would like to show you a short video clip about Liquid net so the concept will be more vivid and tangible Well Now , in order to find the requirment First I would like to say the first main...
  • Periodic Table Families Project - Kyrene School District

    Periodic Table Families Project - Kyrene School District

    Family Album. For this project, your group will be assigned a family from the periodic table. Your group will make a "family album" power point of the elements in your family. You will divide up the elements between the members...
  • Bell Ringer - Loudoun County Public Schools

    Bell Ringer - Loudoun County Public Schools

    Bell Ringer . Pull out Ch 18 ... 4.2 Summarize the impact of cultural changes in the West, including the renaissance and Reformation . ... Kings ruled their people until guns allowed autocratic regime to come to power, conquer neighbors...