Understanding Complexity Theory: Decidability, Undecidability, and Reductions
Explore the concepts of decidability and undecidability in complexity theory, discussing the proof of undecidability for various languages. Learn about the acceptance problem and reductions, including mapping reductions, to relate and solve different computational problems effectively.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
CMSC 28100 Introduction to Complexity Theory Complexity Theory Spring 2024 Instructor: William Hoza 1
Which languages are decidable? Which languages are decidable? 2
Undecidability First, we proved that SELF-REJECTORS is undecidable Then, we used the fact that SELF-REJECTORS is undecidable to prove that HALT is undecidable Then, we used the fact that HALT is undecidable to prove that other interesting languages are undecidable 3
The acceptance problem Let ATM= { ?,? :? is a Turing machine that accepts input ?} Claim: ATM is undecidable Proof by contradiction: Assume that ?decides ATM Let s design an algorithm that decides HALT. Given ?,? : 1. Construct ? , where ? is a modified version of ? in which all rejecting transitions have been changed into accepting transitions 2. Simulate ? on ? ,? . If it accepts, accept; if it rejects, reject. 4
Reductions The proof strategy we have been using is called a reduction A reduction is a way of relating one problem to another problem Informal definition: Problem A reduces to problem B means A solution to problem B would imply a solution to problem A 5
Reductions Example: Suppose I bring my daughter to a zoo in Mexico. She asks, Do they have octopuses? Do they have camels? Do they have gorillas? Do they have My job is to solve problem A: Given an animal name in English, determine whether it s at the zoo A helpful zoo employee can solve problem B: Given an animal name in Spanish, determine whether it s at the zoo We can reduce problem A to problem B by translating from English to Spanish 6
Mapping reductions There are multiple kinds of reductions in computer science In this course, we will focus on a kind of reduction called a mapping reduction 7
? octopus = pulpo Mapping reductions ? = Google Translate Let ?1 and ?2 be languages over the alphabets 1 and 2 respectively 2 such Definition: A mapping reduction from ?1 to ?2 is a function ?: 1 that For every ? ?1, we have ? ? ?2 YES maps to YES ?1, we have ? ? ?2 For every ? 1 NO maps to NO The function ? is computable, i.e., there exists a Turing machine ? such that for every , ? halts on input ? with ? ? written on its tape (followed by blanks) ? 1 8
Mapping reductions Informally, a mapping reduction from ?1 to ?2 is a way of converting instances of ?1 into equivalent instances of ?2 Note: Any string ? is called an instance of ? ?2 ?1 2 1 9
Using reductions to prove decidability Suppose there exists a mapping reduction ? from ?1 to ?2 Claim: If ?2 is decidable, then ?1 is decidable : Proof: Given ? 1 1. Compute ? ? 2 (this is possible because ? is computable) 2. Check whether ? ? ?2 (this is possible because ?2 is decidable) 3. Accept if ? ? ?2 and reject if ? ? ?2 10
Using reductions to prove decidability Algorithm that decides ?1 ? ? Algorithm that Algorithm that Acc/Rej ? computes ? decides ?2 The mapping reduction is ? 11
Using reductions to prove undecidability Suppose there exists a mapping reduction ? from ?1 to ?2 Claim: If ?1 is undecidable, then ?2 is undecidable Proof: If ?2 were decidable, then ?1 would be decidable 12
Using reductions to prove undecidability Strategy for proving that some language ? is undecidable: Identify a suitable language ?HARD that we previously proved is undecidable Design a mapping reduction ? from ?HARD to ? Make sure you do the reduction in the correct direction! The amazing thing about this strategy is that the existence of one algorithm implies the nonexistence of another! 13
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 14
