Class co-NP and EXP in Computational Complexity Theory
Lecture highlights Class co-NP and EXP along with diagonalization in Computational Complexity Theory. It covers the relationship between search and decision problems in NP, examples of NP-complete problems from number theory, and two types of polynomial-time reductions. The content delves into various theorems and claims in the context of complexity theory.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
18.404/6.840 Lecture 10 Last time: - The Reducibility Method for proving undecidability and T-unrecognizability - General reducibility - Mapping reducibility Today: (Sipser 5.2) - The Computation History Method for proving undecidability - The Post Correspondence Problem is undecidable - Linearly bounded automata - Undecidable problems about LBAs and CFGs
Remember To prove some language ? is undecidable, show that ?TM (or any known undecidable language) is reducible to ?.
Revisit Hilberts 10th Problem Recall ? = ? polynomial ? ?1,?2, ,?? = 0 has integer solution) Hilbert s 10th problem (1900): Is ? decidable? Theorem (1971): No Proof: Show ?TM is reducible to ?. [would take entire semester] Do toy problem instead which has a similar proof method. Toy problem: The Post Correspondence Problem. Method: The Computation History Method.
Post Correspondence Problem Given a collection of pairs of strings as dominoes: ?1 ?1, ?2 ?2 , , ?? ? = ?? a match is a finite sequence of dominos in ? (repeats allowed) where the concatenation of the ? s = the concatenation of the ? s. ??? ??? Match = ??1 ??2 ??2 where ??1??2 ??? = ??1??2 ??? ??1 ab aba ,baab aa , abab aba , ba Check-in 10.1 Example: ? = Problem: Given ?, is there a match? Theorem: Undecidable! Let ?1= b baab aaba , ba ab , ab ba Let ??? = Proof: Show ?TM is reducible to ???. First: the Computation History Method. (b) No. ? ? has a match } Does ?1 have a match? (a) Yes. a b a a b a a a a b a b a b a a b a a a a b a b Match: Check-in 10.1
TM Configurations Defn: A configuration of a TM is a triple (?,?,?) where ? = the state, ? = the head position, ? = tape contents representing a snapshot of the TM at a point in time. 6 Configuration: (?3,6,aaaaaabbbbb) Encoding as a string: aaaaa?3abbbbb a a a a a a b b b b b ?3 ?1 ?2 Encode configuration (?,?,?) as the string ?1??2 where ? = ?1?2 and the head position is on the first symbol of ?2.
TM Computation Histories Defn: An (accepting) computation history for TM ? on input ? is a sequence of configurations ?1,?2, ,?accept that ? enters until it accepts. Encode a computation history ?1,?2, ,?accept as the string ?1 # ?2 # # ?accept where each configuration ?? is encoded as a string. ?1 # ?2 # ?3 # # ?accept A computation history for ? on ? = ?1?2 ??. Here say ? ?0,?1 = (?7,a,R) and ? ?7,?2 = (?8,c,?). ?0?1?2 ?? a?7?2 ?? ac?8?3 ?? ?accept # # # #
Linearly Bounded Automata Defn: A linearly bounded automaton (LBA) is a 1-tape TM that cannot move its head off the input portion of the tape. LBA a a b a a b a Tape size adjusts to length of input. Let ?LBA= ?,? LBA ? accepts ? } Theorem: ?LBA is decidable Proof: (idea) If ? on ? runs for long, it must be cycling. Claim: For inputs of length ?, an LBA can have only ? ? ? different configurations. Therefore, if an LBA runs for longer, it must repeat some configuration and thus will never halt. Decider for ?LBA: ?A LBA= On input ?,? 1. Let ? = |?|. 2. Run ? on ? for ? ? ? steps. 3. If has accepted, accept. 4. If it has rejected or is still running, reject. must be looping
?LBA is undecidable Let ?LBA= Theorem: ?LBA is undecidable Proof: Show ?TM is reducible to ?LBA. Uses the computation history method. Assume that TM ? decides ?LBA Construct TM ? deciding ?TM ? = on input ?,? 1. Construct LBA ??,? which tests whether its input ? is an accepting computation history for ? on ?, and only accepts ? if it is. ? ? is an LBA and ? ? = } ??,?= On input ? 1. Check if ? begins ?1# where ?1 is start config of ? on ?. 2. Check that each ??+1 legally follows from ?? for each ?. 3. Check that final configuration is accepting. 4. Accept if all checks pass. Reject if any fail. (c) I m baffled. (d) I wish I was in 6.046. Check-in 10.2 What do you think of the Computation History Method? Check all that apply. (a) Cool ! (b) Just another theorem. 2. Use ? to determine whether ? ??,? = . 3. Accept if no. Rejectif yes. ?0?1?2 ?? a?7?2 ?? ac?8?3 ?? # # # # ?accept ??,? ?1 ?2 ?3 ?accept No additional tape is needed so is an LBA. Check-in 10.2
??? is undecidable Recall ??? = ? ? has a match } Theorem: ??? is undecidable Proof: Show ?TM is reducible to ???. Uses the computation history method. Technical assumption: Match must start with ?1 ?1. Can fix this assumption. Assume that TM ? decides ??? Construct TM ? deciding ?TM ? = on input ?,? 1. Construct PCP instance ??,? where a match corresponds to a computation history for ? on ?. 2. Use ? to determine whether ??,? has a match. 3. Accept if yes. Rejectif no.
Constructing ??,? Make ??,? where a match is a computation history for ? on ?. ?1 ?1= # #?0?1 ??#(starting domino) Check-in 10.3 For each ?,? and ?,? ? where ? ?,? = (?,?,R) What else can we now conclude? Choose all that apply. (a) ??? is T-unrecognizable. ?0? ?0? in ??,? and put ?1 (Handles right moves. Similar for left moves.) Ending dominos to allow a match if ? accepts: ?1 in ??,? and #1 #1 also #1 #1 #1 put #1 (b) ??? is T-unrecognizable. (c) Neither of the above. ?accept ##1 #1 ?1?accept ?accept ?accept ?1 ?accept # ?02 2 3 # # # ?accept # # Illustration: ? = 223 ? ?0,2 = (?7,4,R) Match completed! . . . . . . one detail needed. # ?accept # # # ?02 2 3 # 4 ?72 3 # # ?accept # Check-in 10.3
???CFG is undecidable ? ? is a CFG and ? ? = } Let ???CFG= Theorem: ???CFG is undecidable Proof: Show ?TM is reducible to ???PDA via the computation history method. Assume TM R decides ???PDA and construct TM ? deciding ?TM. ? = On input ?,? 1. Construct PDA ??,? which tests whether its input ? is an accepting computation history for M on w, and only accepts ? if it is NOT. 2. Use ? to determine whether ? ??,? = . 3. Accept if no. Rejectif yes. ??,? operation: ?? ?1 Nondeterministically push some ?? and pop to compare with ??+1. Acceptif invalid step of M, or if start wrong, or if end isn t accepting. ?0?1?2 ?? a?7?2 ?? ac?8?3 ?? # # # # ?accept ??,? ?2 ?2 ?2 ?3 ?accept ?1 ?0 Reverse even-numbered ??to allow comparing with ??+1 via stack.
Computation History Method - recap Computation History Method is useful for showing the undecidability of problems involving testing for the existence of some object. ? Is there an integral solution (to the polynomial equation)? ?LBA Is there some accepted string (for the LBA)? ??? Is there a match (for the given dominos)? ???CFG Is there some rejected string (for the CFG)? In each case, the object is the computation history in some form.
Quick review of today 1. Defined configurations and computation histories. 2. Gave The Computation History Method to prove undecidability. ?LBAis decidable. 3. ?LBAis undecidable. 4. 5. ??? is undecidable. 6. ???CFGis undecidable.
Eliminating the technical assumption Technical assumption: Match must start with ?1 Fix this assumption as follows. ?1. ?1 ?1, ?2 ?2 , , ?? where we require match to start with ?1 Let ? = ?? ?1. ?2 , , ?? ?1 ?1, ?2 ?1 ?1, Create new ? = ?? For any string ? = ?1, ,??, let ? = ?1 ?2 ?? ? = ?1 ?2 ?? ? = ?1 ?2 ?? ?1 ?1 , ?1 ?1 , ?2 ?2 , , ?? ?? , $ Then let ? = $0
