Undecidability in Complexity Theory
Explore the undecidability of the Posts Correspondence Problem (PCP) and its modified version (MPCP) in Complexity Theory. Delve into reductions from the Halting Problem, illustrating the profound implications of undecidability. Understand how the existence of matches in PCP and MPCP scenarios showcases the limitations of computational processes.
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
CMSC 28100 Introduction to Complexity Theory Complexity Theory Spring 2024 Instructor: William Hoza 1
Posts Correspondence Problem Given:a set of dominos ?3 ?3 ?? ?? ?1 ?1 ?2 ?2 Goal: Determine whether it is possible to generate a match ??5 ??5 ??? ??? ??3 ??3 ??1 ??1 ??2 ??2 ??4 ??4 in which the sequence of symbols on top equals the sequence of symbols on the bottom Using the same domino multiple times is permitted 2
Posts Correspondence Problem is undecidable Define PCP = { ,?1, ,??,?1, ,?? ?1, ,?? such that ??1 ???= ??1 ???} Theorem: PCP is undecidable Proof outline: Step 1: Show that a modified version ( MPCP ) is undecidable by reduction from HALT Step 2: Show that PCP is undecidable by reduction from MPCP 3
Modified PCP MPCP = { ,?1, ,??,?1, ,?? ?1, ,?? such that ?1??1 ???= ?1??1 ???} The difference between PCP and MPCP: In MPCP, matches must start with the first domino 4
Reduction from HALT to MPCP Reduction is computable We produce the following dominos: ? ?accept# ? ?reject# ? # # # , ?0? # , , , and # ?? ? ? for every ?,?,? ,? such that ? ?,? = (? ,? ,R) and ? ?accept,?reject ??? for every ?,?,? ,? ,? such that ? ?,? = (? ,? ,L) and ? ?accept,?reject ? ?? ?? ? ?? ? ? ? for every ? and ? ?accept,?reject , , and 5
YES maps to YES Suppose ? halts on ? Under this assumption, we showed last time how to construct a match The construction was based on the computation history of ? on ?: ? ?? 1 ?? ?0 ?1 ?? 1 ?? ?0 ?1 ?1 ?2 ?1 ?2 ??# ? # # # # # # # # # # # # # ?0? # # # # 6
NO maps to NO Suppose ? loops on ?. Let ?0,?1,?2, be the computation history of ? on ? (an infinite sequence of configurations) Assume, for the sake of contradiction, that there is a match We will show by induction that for every ? , there exist ?,? and ? such that ? ?, there are at least ? dominos in the match, and the ? first ? dominos form the following super-domino: ??? ?# ? Base case ? = 0: By definition of MPCP, the match must start with ?0? # 7
NO maps to NO When we are computing ? ?,? , how do we know whether there is a match? A: We simulate ? on ? and observe what happens B: We inspect the transition function of ? ? Inductive step: Assume that the first ? dominos in the match form C: We do not know whether there is a match, and that s okay ??? ?# D: We do not know whether there is a match, and that s an issue Subsequent dominos must spell out ?? ?# on top Respond at PollEv.com/whoza or text whoza to 22333 Exercise: There are only two possible ways to do this, namely ?? ? # # # followed by either ??+1 ? or # Either way, the inductive step is complete Consequence: The match is infinitely long, a contradiction 8
NO maps to NO This completes the proof that MPCP is undecidable We designed a mapping reduction from HALT to MPCP If MPCP were decidable, then HALT would be decidable too 9
Posts Correspondence Problem is undecidable Define PCP = { ,?1, ,??,?1, ,?? ?1, ,?? such that ??1 ???= ??1 ???} Theorem: PCP is undecidable Proof outline: Step 1: Show that a modified version, MPCP, is undecidable by reduction from HALT Step 2: Show that PCP is undecidable by reduction from MPCP 10
Reduction from MPCP to PCP For each string ? = ?1?2 ??, define ? = ?1 ?2 ?? Reduction: ?3 ?3 ?? ?? ?3 ?3 ?? ?? ?1 ?1 ?2 ?2 ?1 ?1 ?1 ?1 ?2 ?2 ? ? = Computable 11
YES maps to YES ??3 ??3 ??? ??? ??1 ??1 ??2 ??2 ??4 ??4 ?1 ?1 Suppose the MPCP instance has a match Then the constructed PCP instance also has a match: ??? ??? ??1 ??1 ??2 ??2 ?1 ?1 ? 12
NO maps to NO We prove the contrapositive. Suppose the constructed PCP instance has a match ?1 ?1 Must start with because that s the only domino with the same first symbol on top and on bottom Delete all the symbols from the match, and we get a match for the original MPCP instance 13
Using reductions to prove undecidability OBJECTION: I don t like mapping reductions. I preferred our first few undecidability proofs, where we did proofs by contradiction and the concept of a reduction was implicit. RESPONSE 1: Mapping reductions help us to reason clearly about undecidability RESPONSE 2: You should get comfortable with the concept of a mapping reduction now in preparation for what will come later The concept might feel optional now, but later it will be essential 14
Given ?,?, how would we compute ? ?,? ? The emptiness problem A: Simulate ? on ?, and if it ever halts, accept B: Simulate ? on ? and construct ? based on simulation results C: Modify the transition function D: There does not exist an algorithm that computes ? Let ETM= ? there does not exist ? such that ? accepts ? of ? to construct ? Respond at PollEv.com/whoza or text whoza to 22333 Claim: ETM is undecidable Proof: We will design a mapping reduction from HALT to ETM = ? , where ? is a TM that does the following on input ?: Let ? ?,? 1. Simulate ? on ? 2. If ? ever halts, accept YES maps to YES Computable NO maps to NO 15
Which languages are undecidable? Which languages are undecidable? 16
Some more undecidable problems We have seen several interesting examples of undecidable problems To wrap up our discussion of undecidability, I ll mention a few more examples of undecidable problems but we won t do the proofs (This material will not be on problem sets or exams) 17
Hilberts 10th problem Problem: Given a polynomial equation with integer coefficients such as ?2+ 3?? + ?3+ ?2?2= 4??2+ 6?? + 2, determine whether there is an integer solution Let HILBERT10 = { ?,? ? such that ? ? = ? ? } Theorem: HILBERT10 is undecidable 18
Derivatives vs. Integrals Recall: Calculus Computing derivatives is mechanistic Sum rule ? + ? = ? + ? , product rule ?? = ? ? + ?? , chain rule ? ? = ? ? ? , etc. In contrast, computing integrals seems to involve creativity ?-substitutions, integration by parts, etc. 19
Elementary functions Definition: A function ?: is elementary if it can be defined by a formula using addition, multiplication, rational constants, powers, exponentials, logarithms, trigonometric functions, and ? E.g. ? ? = ? sin ?4 3? ??? 20
Integration is undecidable Fact: There exist elementary functions that do not have elementary antiderivatives, such as ? ? = ? ?2 Let INTEGRABLE = { ? ? is an elementary function with an elementary antiderivative} Theorem: INTEGRABLE is undecidable 21
