C

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[1] = 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!

Recently Viewed Presentations

  • Record Keeping Clinical levels 1,2, & above Facilitated

    Record Keeping Clinical levels 1,2, & above Facilitated

    Record Keeping Clinical levels 1,2, & above Facilitated learning workshop
  • ARV-trials 2017

    ARV-trials 2017

    SWORD-1 & 2 Studies: Switch to DTG + RPV Conclusion A switch to a novel, once-daily 2 drug-regimen of DTG + RPV demonstrated high efficacy and was non-inferior to the continuation of a combined antiretroviral therapy in virologically suppressed HIV-1-infected...
  • The Federal Reserve

    The Federal Reserve

    The First Bank of the United States (BUS) Only bank with federal charter. Mercantilist movement behind banks. Fed owns 20%, deposits funds here. BUS buys government debt; issues notes.
  • T H B E P U Z Z

    T H B E P U Z Z

    Total Entropy and the lattice EOS The HBT puzzle Explanations to the HBT Puzzle Tsunamis at RHIC Modeling Tsunamis at RHIC with Hydrodynamics Hydrodynamic Evolution L=2 GeV/fm3, c2mixed=0.05 HBT Radii Viscosity and Tsunamis: Initial-State Asymmetry of Tij Non-Zero Shear Bulk...
  • River Valleys - isjgorj.ro

    River Valleys - isjgorj.ro

    Dinamica placilor tectonice şi deriva continentelor folosind imagini Ce se intâmplă după? (What happens next?) What happens next? Ce se întâmplă după....
  • RAILROAD COMMISSION OF TEXAS How to Submit Oil

    RAILROAD COMMISSION OF TEXAS How to Submit Oil

    Only complete if Multiple Completion - not for workovers or downhole commingled wells. Rotation Time Within Surface Casing is a REQUIRED item. 6/10/2014. W-2 Page 4. Depth found on GAU Letter * Per SWR 13(b)(5)(a) All Flowing Oil wells must...
  • Virginia Department of Education Module Eleven Driver Responsibilities

    Virginia Department of Education Module Eleven Driver Responsibilities

    It adds weight to your car, but the savings are guaranteed to be more than the cost of the extra weight. The best options are things that can be pre-cooked and keep well or food that doesn't require cooking at...
  • Creating a Culture of Performance to Support Continual

    Creating a Culture of Performance to Support Continual

    Read voraciously, and listen to learn, then teach and share everything you know. ... Define your distinctive strategic position. Support operational effectiveness - the nuts and bolts of management. Provide tools to reach targets and consequences for missing targets. Transformation...