Understanding Time Complexity and Computability in Theory of Computation

CSE 105 THEORY OF COMPUTATION Spring 2025 https://cseweb.ucsd.edu/classes/sp25/cse105-a/

Today's learning goals Sipser Ch 7 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.

Complexity theory Chapter 7 In the "real world", computers (and Turing machines) don't have infinite tape, and we can't afford to wait unboundedly long for an answer. "Decidable" isn't good enough we want "Efficiently decidable"

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? average- case? Expect to have to spend more time on larger inputs.

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 worst- case? average-case? Big-O Can we detect problems that are efficiently solvable?

Time complexity For M a deterministic decider, its running time or time complexity is the function f: N N given by f(n) = maximum number of steps M takes before halting, over all inputs of length n. Plus, instead of calculating precisely, estimate f(n) by using big-O notation. worst-case analysis

Time complexity classes TIME(t(n)) = { L | L is decidable by a TM running in O(t(n)) } Brute-force search Exponential Polynomial Includes many everyday algorithms. Invariant under many models of TMs

What about nondeterminism? q0 q0 non- deterministic computation deterministic computation qacc qacc qrej qrej qrej

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

Time complexity For M a deterministic decider, its running time or time complexity is the function f: N N 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 N 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 }

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 } Is DTIME(n2) a subset of DTIME(n3)? A. Yes B. No C. Not enough information to decide D. I don't know

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 } Is DTIME(n2) a subset of NTIME(n2)? A. Yes B. No C. Not enough information to decide D. I don't know

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 } Is NTIME(n2) a subset of DTIME(n2)? A. Yes B. No C. Not enough information to decide D. I don't know

P vs NP

P = polynomial time Problems that can be solved in time O(nk) for some fixed k Linear: O(n) Quadratic: O(n2) Can't use nondeterminism Can use multiple tapes Often need to be more clever than na ve / brute force approach

Examples of problems in P PATH = {<G,s,t> | G is graph with n nodes with path from s to t} Use breadth first search REL-PRIME = { <x,y> | x and y are relatively prime integers} Use Euclidean algorithm CFG-GEN = {<G,w> | G is a CFG, w is generated by G} Use dynamic programming All of these can be solved in polynomial time Algorithms research: find fastest algorithm

NP = verifiable in polynomial time NP are problems that a solution can be verified in polynomial time Contrast with P, where we can find a solution in polynomial time Equivalently: NP = problems that can be solved by a nondeterministic polynomial time TM

Examples of problems in NP HAMILTONIAN = {<G> | G is graph with n nodes, and there is path that goes through every node exactly once} CLIQUE = { <G,k> | G is an undirected graph with n nodes that has a k-clique} SAT = { <X> | X is a satisfiable Boolean formula with n variables}

Example: CLIQUE CLIQUE = { <G,k> | G is an undirected graph with n nodes that has a k-clique} k-clique: set of k nodes all connected to each other To find it, (naively) need time O(nk) Best known algorithm takes time ~O(nk/3) To verify it, need time O(k2) much faster!

P vs NP The P vs NP question asks: if we can verify a solution efficiently (in polynomial time), can we also find it efficiently? Most people believe the answer is NO, but we have absolutely no clue how to prove it This is one of the Millenium problems Solving it will get you $1M !!!

Decidable Decidable NP P = NP or P Finite Finite

P vs. NP Problems in P (Membership in any) CFL PATH EDFA EQDFA Addition, multiplication of integers Problems in NP Any problem in P HAMPATH CLIQUE VERTEX-COVER TSP SAT

How to answer P = NP ? Are there hardest NP problems? If so, finding an efficient solution for one of them would guarantee that all NP problems have efficient solutions.

Reductions to the rescue Sipser p. 299-305 In 1970s Stephen Cook and Leonid Levin indepdendently and in parallel lay foundations of NP-completeness Definition A language B is NP-complete if: (1) it is in NP; and (2) every language in NP is polynomial-time reducible to it. Consequence If an NP-complete problem has a polynomial time solution then all NP problems are polynomial time solvable.

What would prove that P = NP? A. Showing that a problem solvable by brute- force methods has a nondeterministic solution. B. Showing that there are two distinct NP- complete problems. Reductions to the rescue Sipser p. 299-305 In 1970s Stephen Cook and Leonid Levin indepdendently and in parallel lay foundations of NP-completeness C. Finding a polynomial time solution for an NP- complete problem. D. Proving that an NP-complete problem is not solvable in polynomial time. E. I don't know Definition A language B is NP-complete if: (1) it is in NP; and (2) every language in NP is polynomial-time reducible to it. Consequence If an NP-complete problem has a polynomial time solution then all NP problems are polynomial time solvable.

3-SAT Rosen p. 299 Cook-Levin Theorem: 3-SAT is NP-complete. 3-SAT = { <Boolean formulas in CNF with exactly 3 literals/clause> | there is a truth assignment to variables that makes formula evaluate to T}

Are other problems NP-complete? To prove that some language is NP-complete From scratch: Prove it is NP, and that all NP problems are polynomial-time reducible to it. Using reduction: Show that a (known-to-be) NP complete problem reduces to it.

NP-complete problems There are MANY examples of NP-complete problems A few that we saw: 3-SAT CLIQUE HAMILTONIAN PATH

Solving NP complete problems Unfortunately, many real-life problems end up being NP complete But we still want to solve them Approaches: 1. Exponential algorithms (if inputs are small enough) 2. Heuristics, domain knowledge (special cases) 3. Find approximate solutions (approximation algorithms)

[source: xkcd]