Complexity Classes: Hierarchy Theorems, Exponential Problems, and Intractability

18.404/6.840 Lecture 22 Last time: - Finished NL = coNL - Time and Space Hierarchy Theorems Today: (Sipser 9.2) - A natural intractable problem - Oracles and P versus NP Posted: - Solutions to Problem Set 5 - Problem Set 6

Review: Hierarchy Theorems Theorems: SPACE ? ? ? ,SPACE ? ? for space constructible ?. , TIME ? ? for time constructible ?. TIME ? ? ? /log ? ? TIME 2? SPACE 2? SPACE ?3SPACE ?4 TIME ?4 TIME ?3 TIME ?2 SPACE ?2 Check-in 22.1 Which of these are known to be true? Check all that apply. (a) TIME 2? , TIME 2?+1 (b) TIME 2? , TIME 22? (c) NTIME ?2 , PSPACE (d) NP , PSPACE ???? Corollary: NL , PSPACE PSPACE NL Implies ???? NL because the polynomial-time reductions in the proof that ???? is PSPACE-complete can be done in log space. Check-in 22.1

Exponential Complexity Classes Defn: EXPTIME = ?TIME 2?? EXPSPACE = ?SPACE 2?? Time Hierarchy Theorem L NL P NP PSPACE EXPTIME EXPSPACE Space Hierarchy Theorem Defn: ? is EXPTIME-complete if 1) ? EXPTIME 2) For all ? EXPTIME, ? P? Same for EXPSPACE-complete Theorem: If B is EXPTIME-complete then ? P Theorem: If B is EXPSPACE-complete then ? PSPACE (and ? P) intractable Next will exhibit an EXPSPACE-complete problem

A Natural Intractable Problem Defn: ??REX= ?1,?2 ?1 and ?2are equivalent regular expressions} Theorem: ??REX PSPACE Proof: Later (if time) or exercise (uses Savitch s theorem). ? Notation: If ? is a regular expression write ?? to mean ?? ? Defn: ??REX = ?1,?2 ?1 and ?2are equivalent regular expressions with exponentiation} (exponent is written in binary). Theorem: ??REX is EXPSPACE-complete Proof: 1) ??REX EXPSPACE 2) If ? EXPSPACE then ? P??REX 1) Given regular expressions with exponentiation ?1 and ?2, expand the exponentiation by using repeated concatenation and then use ??REX PSPACE. The expansion is exponentially larger, so gives an EXPSPACE algorithm for ??REX . 2) Let ? EXPSPACE be decided by TM ? in space 2??. Give a polynomial-time reduction ? mapping ? to ??REX .

Showing ?P??REX Theorem: ??REX is EXPSPACE-complete Proof continued: Let ? EXPSPACE decided by TM ? in space 2??. Give a polynomial-time reduction ? mapping ? to ??REX . ? ? = ?1,?2 ? ? iff ? ?1 = ? ?2 Construct ?1 so that ? ?1 = all strings except a rejecting computation history for ? on ?. Construct ?2= ( is the alphabet for computation histories, i.e., = ? # ) ?1 construction: ?1= ?bad start ?bad move ?bad reject Rejecting computation history for ? on ?: Check-in 22.2 Roughly estimate the size of the rejecting computation history for ? on ?. 2?? 2?? 2?? Pad all configurations with blanks to have length 2?? (a) 2? (c) 22?? (b) 2?? # # # ababa abababa ?0?1?2 ?? ?reject ?1= ?start ?2 ?reject Check-in 22.2

?P??REX (?badstart) Construct ?1 to generate all strings except a rejecting computation history for ? on ?. ?1= ?bad start ?bad move ?bad reject Rejecting computation history for ? on ?: 2?? 2?? 2?? # # # ababa abababa ?0?1?2 ?? ?reject ?1= ?start ?2 ?reject ?0= ?0 ?1= ?1 ?2= 2 ?2 ??= ? ?? ??+1= ?+1 ? ?2(??) 1= 2(??) 1 ? ?#= 2(??) # ?bad start generates all strings that do not start with ?start= ?0?1?2 ?? ?bad start= ?0 ?1 ?2 ?? ?blanks ?# Remember: is the alphabet for computation histories, i.e., = ? # ) Notation: ? = {?} b= without b ?blanks= ?+1 ?2?? (?+2) ? 7= all strings of length 7 7 = all strings of length 0 thru 7 ? all strings of length ? + 1 thru 2(??) 1

?P??REX (?badmove & ?badreject) Construct ?1 to generate all strings except a rejecting computation history for ? on ?. ?1= ?bad start ?bad move ?bad reject Rejecting computation history for ? on ?: 2?? 2?? 2?? # # # ababa abababa ?0?1?2 ?? ?reject ?reject ?2 ?1= ?start ?bad reject generates all strings that do not contain ?reject ?bad reject= ?reject ?bad move generates all strings that contain an illegal 2 3 neighborhood abc 2?? 2?? 2 ?bad move= 2def abc def illegal a b ?? ??+1 c d e f

Computation with Oracles Let ? be any language. Defn: A TM ? with oracle for ?, written ??, is a TM equipped with a black box that can answer queries is ? ?? for free. Example: A TM with an oracle for ??? can decide all ? NP in polynomial time. Defn: P?= ? ? is decidable in polynomial time with an oracle for ?} Thus NP P??? NP = P???? Probably No because coNP P??? Defn: NP?= ? ? is decidable in nondeterministic polynomial time with an oracle for ?} Recall MIN-FORMULA = ? ? is a minimal Boolean formula } Example: MIN FORMULA NP??? On input ? 1. Guess shorter formula ? 2. Use ??? oracle to solve the coNP problem: ? and ? are equivalent 3. Accept if ? and ? are equivalent. Rejectif not.

Oracles and P versus NP Theorem: There is an oracle ? where P?= NP? Proof: Let ? = ???? NP???? NPSPACE = PSPACE P???? Relevance to the P versus NP question Recall: We showed ??REX PSPACE. Could we show ??? P using a similar method? NO. Check-in 22.3 Which of these are known to be true? Check all that apply. Reason: Suppose YES. The Hierarchy Theorems are proved by a diagonalization. In this diagonalization, the TM ? simulates some TM ?. If both TMs were oracle TMs ?? and ?? with the same oracle ?, the simulation and the diagonalization would still work. Therefore, if we could prove P NP by a diagonalization, we would also prove that P? NP? for every oracle ?. But that is false! (a) P???= P??? (b) NP???= coNP??? (c) MIN-FORMULA P???? (d) NP????= coNP???? Check-in 22.3

Quick review of today 1. Defined EXPTIME and EXPSPACE 2. Defined EXPTIME- and EXPSPACE-completeness 3. Showed ??REX is EXPSPACE-complete and thus ??REX PSPACE 4. Defined oracle TMs 5. Showed P?= NP? for some oracle ? 6. Discussed relevance to the P vs NP question

??REX PSPACE Theorem: ??REX PSPACE Proof: Show ??RE? NPSPACE On input ?1,?2 [ assume alphabet ] 1. Convert ?1 and ?2 to equivalent NFAs ?1 and ?2 having ?1 and ?2 states. 2. Nondeterministically guess the symbols of a string ? of length 2?1+ ?2 and simulate ?1 and ?2 on ?, storing only the current sets of states of ?1 and ?2. 3. If they ever disagree on acceptance then accept. 4. If always agree on acceptance then reject.