Introduction to Adleman's Theorem in Complexity Theory
Explore the intriguing concept of Adleman's Theorem in Complexity Theory, which offers insights into the relationship between P, BPP, and PSIZE. Discover how random bits play a crucial role in proving this theorem and its implications for the P versus BPP conjecture.
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
PSIZE Adleman s theorem BPP Last class, we showed that P PSIZE P We got started proving a stronger theorem: Adleman s Theorem: BPP PSIZE Adleman s theorem is tantalizingly similar to the statement P = BPP 2
Proof of Adlemans theorem (BPP PSIZE) Proof: Let ? BPP where ? Amplification lemma There exists a polynomial-time randomized Turing machine ? such that for every ? and every ? ?: If ? ?, then Pr ? accepts ? > 1 1/ ? If ? ?, then Pr ? rejects ? < 1 1/ ? Let ? ? be the time complexity of ? 3
Random bits: Good for all inputs simultaneously Claim: For every ?, there exists ? 0,1? ?that is good for all ? ? I.e., if we initialize ? with ? on tape 1 and ? on tape 2, then it will correctly accept/reject depending on whether ? ? We proved the claim last class Now let s use the claim to prove Adleman s theorem 4
Constructing the circuit Let ? = ?#? ? accepts ? when tape 2 is initialized with ? Then ? P PSIZE Let ? . Our job is to construct a circuit that computes ?? Let ? be an optimal circuit that computes ?? where ? = ? + 1 + ? ? If ? is good for ?, then ? ?#? = ?? ? 5
Constructing the circuit ? ? ?2 ?3 ?4 ?5 ?6 ?7 ??? ?2 ??? ?1 ?1 1 0 0 1 1 #? hard-coded into circuit ? computes ??, and it has size ? ? ??= ? ? + 1 + ? ? = poly ? 6
Adlemans theorem and P vs. BPP Adleman s theorem (BPP PSIZE) does not resolve the question of whether P = BPP However, after seeing Adleman s theorem, I hope that the conjecture P = BPP is starting to look plausible The conjecture can be supported by more compelling evidence, but it s beyond the scope of this course 7
BPP and the Extended Church-Turing Thesis Let ? be a language Extended Church-Turing Thesis: It is physically possible to build a device that decides ? in polynomial time if and only if ? P. Assuming P = BPP, the extended Church-Turing thesis survives the challenge posed by randomized computation! 8
BPP and the Extended Church-Turing Thesis Just in case, the thesis is sometimes revised to allow randomization: Extended Church-Turing Thesis, version 2: Let ? be a language. It is physically possible to build a device that decides ? in polynomial time if and only if ? BPP. This version is immune to the challenge posed by randomization However, there is a bigger threat: Quantum Computation 9
Quantum computing Properly studying quantum computing is beyond the scope of this course We will circle back to it later to discuss some key facts For now, let s stick with P as our model of efficient computation Because of quantum computing, P should probably not be considered the ultimate model of efficient computation, but it is still a valuable model 10
Which problems Which problems can be solved can be solved through computation? through computation? 11
Which languages are in Which languages are in P P? ? 12
in P P? ? Which languages are Which languages are not not in 13
Intractability vs. undecidability How can we prove that certain languages are outside P? Certainly HALT P Is every decidable language in P? This would mean that every algorithm can be modified to make it run in polynomial time! 14
Intractability vs. undecidability HALT All languages Decidable languages ??? P PALINDROMES 15
To prove this theorem, what should we prove? The Time Hierarchy Theorem A: The function ?3 grows faster than functions that are ? ? B: Every Turing machine has time complexity ?3 Let ?: be a reasonable time complexity bound (we will come back to this) C: There exists ? TIME ? ? such that ? TIME ?3 D: There exists ? TIME ?3 such that ? TIME ? ? Respond at PollEv.com/whoza or text whoza to 22333 TIME ?3 Theorem:TIME ? ? TIME ? ? means the class of languages decidable in time ? ? TIME ? TIME ?3 Note: TIME ? ? Theorem interpretation: Given a little more time, we can solve more problems 16
Proof of the Time Hierarchy Theorem Let ? = { ? ? rejects ? within ? ? steps} Claim 1: Let ? be any Turing machine with time complexity ??? = ? ? ? . Then ? does not decide ?. Proof: Let ? be a modified version of ?, constructed by adding dummy states to artificially inflate ? until ?? ? ? ? If ? accepts ? , then ? ?, and if ? rejects ? , then ? ?! 17
Proof of the Time Hierarchy Theorem Let ? = { ? ? rejects ? within ? ? steps} Claim 2:? TIME ?3 Subtle point: How do we know when we re done? Proof: Given ? , we simulate ? on ? for ? ? steps and check whether it rejects Exercise: Verify that we can simulate a single step of ? using ? ?2 steps Total time complexity: ? ? ?2= ? ?3 18
