# C CIS 262 Automata, Computability, and Complexity Spring 2019 http://www.seas.upenn.edu/~cse262/ Instructor: Aaron Roth [email protected] Lecture: April 8, 2019 A Semester of Bad News Culminating last Wednesday. Most problems are undecidable. And Mathematics is incomplete. Recap: Part B: Computability Theory

ALL LANGUAGES RECOGNIZABLE DECIDABLE Turing Machines: Universal model of computation: Simple and mathematically precise definition Computing power same as general computers Useful to understand the boundary of decidability Classification of problems into decidable, recognizable 3 Part C: Complexity Theory Lets focus just on decidable problems.

In practice of computing, we want a program to solve a problem as fast as possible Complexity theory: How much time and space is needed to solve a problem ? 4 The Class P A language L belongs to the class P if there exists a deterministic halting TM M such that 1. M decides L (that is, L(M) = L ) 2. Time complexity of M is O(nk), for some k. (i.e. on all inputs of length n, M halts after at most O(nk) steps) Strong Church Turing Thesis Deterministic programs and deterministic TMs are equivalent with

time complexities differing by at most a polynomial-factor P is the class of problems solvable in polynomial-time 5 Recap: Nondeterministic Turing Machines a b a a b a a a b q3 _ _ a/x,R q

q1 a/b, L q2 Nondeterministic Turing Machine: Based on current state and current symbol, multiple possible transitions 6 Execution of NTM C0

On input w, initial configuration = (e, q0, w) At every step, multiple possible successors, depending on which transition is chosen Possible execution: Path through this tree Accepting execution: state equals qa Rejecting execution: state equals qr Input w is accepted if some execution is accepting Input w is rejected if all executions are finite and rejecting 7

Polynomial-Time NTM Time complexity of an NTM M is f(n) if on every input w of length n, every execution path terminates after at most f(n) transitions Depth of the execution tree = f(n) thus, the number of possible execution paths is exp(f(n)) Polynomial-time NTM: Time complexity is O(nk), for some constant k 8 Nondeterministic Programs

x = choose (0, 1); if (x=0) { } else { } Value of x is chosen nondeterministically Execution can continue along two paths, one with x = 0 and one with x = 1 Acceptance/rejection similar to NTMs: Accept = acceptance along at least one path Reject = rejection along all paths Time complexity f(n) means

every path terminates in at most f(n) steps 9 Cliques in Undirected Graphs A set U of vertices in an undirected graph G is a clique if every pair of vertices in U is connected by an edge Graph G with a clique of size 5 CLIQUE ={| G is an undirected graph and contains a clique of size k} Write a nondeterministic program to solve this problem 10

Nondeterministic Program for Clique Input: graph G with vertices V (numbered 1 to n) and number k /* Guess which vertices belong to the clique U */ for (i = 1 to n) { U[i] = choose(0, 1) }; /* Check that the guessed subset U indeed forms a clique of size k */ Check that the number of indices i with U[i]=1 equals k; Check that for all distinct indices i, j with i != j, if U[i]=1 and U[j]=1 then there is an edge between i and j in G If both these checks succeed, then accept, else reject Correctness: If (G,k) is in CLIQUE, then at least one execution leads to acceptance, else all executions lead to rejection Complexity: Each execution terminates in polynomial-time 11 The Class NP

A language L belongs to the class NP if there exists a nondeterministic TM M such that 1. M decides L 2. Time complexity of M is O(nk), for some k Nondeterministic TMs = Nondeterministic Programs L can be solved by a program that can nondeterministically choose values resulting in multiple possible executions: 1. When answer is yes, at least one execution leads to acceptance 2. When answer is no, all executions lead to rejection 3. Every execution terminates in polynomial-time CLIQUE is in NP 12 Hamiltonian Path in Directed Graphs

PATH Problem: Given a directed graph G and vertices s and t, check if there is a path from s to t PATH is in P Graph G2 Graph G1 s t s t

A path is called a Hamiltonian path if it visits each vertex exactly once HamiltonianPath Problem: Given a directed graph G and vertices s and t, check if there is a Hamiltonian path from s to t 13 Hamiltonian Path is in NP Input: Directed graph G with vertices V and vertices s and t /* Guess a sequence of vertices from s to t */ p = s; p[n] = t; For ( i = 2 to n-1) { p[i] = choose( u in V) }; /* Check that sequence p of vertices is a Hamiltonian path */ Check that each vertex u in V equals p[i] for exactly one index i; Check that for i = 1 to n-1, there is an edge between p[i] and p[i+1] in G If both these checks succeed, then accept, else reject

Correctness: If is in HamiltonianPath, then at least one execution leads to acceptance, else all executions lead to rejection Complexity: Each execution terminates in polynomial-time 14 NP Algorithms: Guess and Verify Typical structure of NP algorithms: Two phases: 1. Guess a solution (e.g. subset of vertices for Clique) 2. Check that guess is correct (e.g. subset is indeed a clique) Requirements: 1. Size of guess is polynomial in size of input 2. Check can be executed by a polynomial-time algorithm 15

Verifier Based Definition Consider a language L Verifier V for L has two inputs: w and c (called certificate) such that for all inputs w, w is in L if and only if there exists c such that V accepts w Accept (w in L) w c

Reject (otherwise) Accept if c is evidence of w in L Verifier V Reject (otherwise) Polynomial-time verifier means V is a polynomial-time algorithm Implies that |c| is also polynomial in |w| 16

Verifier for CLIQUE Accept if G has clique of size k G k G k CLIQUE Reject

(otherwise) Accept if U is a clique of size k in G U Verifier V Reject (otherwise) Such a verifier can be implemented as a polynomial-time algorithm is in CLIQUE if and only if there exists U s.t. V accepts

17 Verifier for Hamiltonian Path H-PAPTH = { | there is a Hamiltonian Path from s to t in graph G } certificate is a sequence p of vertices Verifier V accepts if p is a Hamiltonian path from s to t in G Such a verifier can be implemented as a polynomial-time algorithm is in H-Path if and only if there exists p s.t. V accepts 18 Equivalent Definitions of NP

Following definitions are equivalent: 1. A language L is in NP if there exists a polynomial-time nondeterministic Turing machine that accepts L 2. A language L is in NP if there exists a polynomial-time deterministic TM V such that w is in L iff V accepts for some c Note: there are many alternative equivalent definitions of NP: e.g. Probabilistically Checkable Proofs 19 Poly-time NTM => Poly-time Verifier Suppose there is NTM M that accepts L and is of time complexity f(n)

On an input w of length n, executions of M are captured by tree of depth f(n) Certificate c = Sequence of 0/1s of length f(n) that encodes path in the execution tree Verifier V: given w and c, execute M on w resolving choices as specified by c, and accept if this path results in acceptance by M M accepts w iff there exists c such that V accepts If f(n) is O(nk), then |c| = O(|w|k) and V is deterministic O(nk) 20 Poly-time Verifier => Poly-time NTM Suppose a language L has a verifier V: V accepts for some c if and only if w is in L V is a deterministic TM of time complexity f(n)

Nondeterministic TM M for L: Given input w of length n, /* Guess the certificate c */ for (i = 1 to f(n)) { c[i] = choose (0,1) } /* check that c is the correct certificate for w */ Run V on ; if V accepts, accept, else reject Time-complexity of M is f(n), and M accepts L If V is a poly-time verifier, than M is poly-time NTM, and L is in NP 21 Graph Coloring Given a graph G, assign colors to vertices so that no edge connects vertices of same color Minimization problem: Find minimum number of

colors that suffice In this example, 3 colors suffice Decision problem: COLOR = { | G can be colored using k colors } 22 Graph Coloring is in NP COLOR = {| G is undirected graph that can be colored using k colors} Verifier V: Given undirected graph G and number k and certificate c, 1. Check if c assigns each vertex in G a number in {1, 2, k} 2. Check for each edge (u,v) in G, c assigns distinct numbers to u and v

Claim: V can be implemented as a polynomial-time algorithm Claim: V accepts for some c if and only if is in COLOR Point of clarification: What is input c to verifier V? Its really a string of symbols (such as 0/1s) Verifier checks if this string encodes the desired certificate (such as assignment from vertices to {1,,k} in this case) 23 Does NP include all decidable problems ? Consider complement of CLIQUE: Given an undirected graph G and k, accept if G does not contain a clique of size k What will be poly-time verifier for this ? How can nondeterminism help to check non-existence of a clique? What evidence can I give you so that you can easily (i.e. in

polynomialtime) convince yourself that no clique exists ? Same holds for complements of other NP problems: Given G and k, check that G cannot be colored using k colors Given G, s and t, check that there is no Hamiltonian path from s to t 24 How does NP relate to P ? Every problem in P is in NP A deterministic machine is just a special case of nondeterministic one We dont know whether P = NP Problems in NP such as CLIQUE may turn out to be in P if someone finds a poly-time deterministic algorithm for it For an NP problem, whats the best deterministic known algorithm

for it? Recall simulation of a nondeterministic TM by a deterministic one 25 The class EXPTIME A language L belongs to EXPTIME if there exists a deterministic TM M for L with time complexity of M is O ( exp ( nk )) Claim: If a language L is in NP, then it is in EXPTIME Proof: Suppose L is in NP. Consider a verifier V for L: Time complexity of V is f(n) and V accepts for some c if and only if w is in L Deterministic TM M for L: Given input w of length n, For each string c of length f(n), Run V on , If V accepts, stop and accept, else continue

Claim: M accepts L and time complexity of M is O( exp (f(n))) Exercise: if Complement of L is in NP then L is in EXPTIME 26 Housekeeping No class on Wednesday April 10. See you next Monday, April 15!