Introduction to Complexity Theory in Spring 2025
Explore the fundamentals of complexity theory with a focus on computational problem-solving, memory models, and robustness in algorithms. Delve into the distinctions between fine-grained and coarse-grained complexity, language classifications in P and P.P, and the intricacies of intractability and undecidability in computing.
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 2025 Instructor: William Hoza 1
Which problems Which problems can be solved can be solved through computation? through computation? 2
MEMORY Word RAM model 010 110 101 110 110 111 000 Word RAM time complexity ?1 110 closely matches time complexity ?2 Control 101 Load/Store in practice on ordinary ?3 110 computers Some version of the word RAM model is typically assumed (implicitly or explicitly) in algorithms courses and the computing industry 3
Robustness of P Let ? 0,1 Theorem: If there is a word RAM program that decides ? in time poly ? , then there is a Turing machine that decides ? in time poly ? . Proof omitted 4
Fine-grained vs. coarse-grained complexity If/when you care about the distinction between ? ? time and ? ?2 time, you should probably use the word RAM model In this course: We focus on the distinction between polynomial time and exponential time We can therefore continue using the Turing machine model 5
Which problems Which problems can be solved can be solved through computation? through computation? 6
Which languages are in Which languages are in P P? ? 7
in P P? ? Which languages are Which languages are not not in 8
Intractability 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! 9
Intractability vs. undecidability HALT All languages Decidable languages ??? P PALINDROMES 10
Intractability vs. undecidability Theorem: There exists ? 0,1 such that ? is decidable, but ? P. ? ? rejects ? within 2? steps Proof: Let ? = On the next three slides, we will show that ? is decidable and ? P 11
Proof that ? is decidable ? ? rejects ? within 2? steps ? = An algorithm that decides ?: Given the input ? : Simulate ? on ? for 2? steps 1. 2. If it rejects within that time, accept 3. Otherwise, reject 12
Which of the following best describes what weve proven? Proof that ? P ? ? rejects ? within 2? steps B: We showed that ? ? > 2? for all ? ? = A: We showed that ? ? > 2? for a single value of ? C: We showed that ? ? > 2? for all sufficiently large ? D: We showed that ? ? > 2? for infinitely many ? Let ? be a TM that decides ? Respond at PollEv.com/whoza or text whoza to 22333 Let ?: be the time complexity of ?, and let ? = ? Does ? accept ? ? No, because that would imply ? ? Does ? reject ? within 2? steps? No, because that would imply ? ? Only remaining possibility: ? rejects ? after more than 2? steps Therefore, ? ? > 2? but this does not imply ? ? poly ? 13
Proof that ? P ? ? rejects ? within 2? steps ? = Let ? be a TM that decides ?, with time complexity ?: Add dummy states! For infinitely many values of ?, there exists a TM ?? such that ?? decides ?, ?? has time complexity ?, and ?? = ? Each ?? must reject ?? after more than 2? steps Otherwise, it would get trapped in a liar paradox Therefore, ? ? > 2? for infinitely many values of ?, hence ? ? poly ? 14
The Time Hierarchy Theorem Using the same proof idea, we can prove a more general theorem: Time Hierarchy Theorem: For every* function ?: such that ? ? ?, there is a language ? TIME ?4 such that ? TIME ? ? . *assuming ?is a reasonable time complexity bound. We will come back to this TIME ? ? means the set of languages that are decidable in time ? ? Given more time, we can solve more problems 15
Proof of the Time Hierarchy Theorem Let ? = ? ? rejects ? within ? ? steps On the next four slides, we will prove: ? TIME ?4 ? TIME ? ? 16
Proof that ? TIME ?4 ? = ? ? rejects ? within ? ? steps An algorithm that decides ?: Given the input ? : Simulate ? on ? for ? ? 1. steps 2. If it rejects within that time, accept 3. Otherwise, reject Time complexity in the TM model? 17
Proof that ? TIME ?4 ? = ? ? rejects ? within ? ? steps Let ? = ? 1?0 ? Each simulated step takes ? ? actual ? steps Total time complexity of multi-tape ? machine: ? ? ? ? ?? 2 ?? 1 ?? ??+1 ??+2 After converting to a one-tape 1? ? machine: ? ? ?2 ?2= ? ? ?4 18
Time-constructible functions Definition: A function ?: is time-constructible if there exists a multi- tape Turing machine ? such that Given input 1?, ? halts with 1? ? written on tape 2 ? has time complexity ? ? ? Our proof that ? TIME ?4 works assuming ? is time-constructible All reasonable time complexity bounds (e.g., 5? or ?2 or 2?) are time- constructible 19
Time Hierarchy Theorem ? = ? ? rejects ? within ? ? steps Time Hierarchy Theorem: For every time-constructible ?: , there is a language ? TIME ?4 such that ? TIME ? ? . We showed ? TIME ?4 We still need to show ? TIME ? ? 20
Proof that ? TIME ? ? ? = ? ? rejects ? within ? ? steps Let ? be a TM that decides ?, with time complexity ? : Add dummy states! For infinitely many values of ?, there exists a TM ?? such that ?? decides ?, ?? has time complexity ? , and ?? = ? Each ?? must reject ?? after more than ? ? steps Otherwise, it would get trapped in a liar paradox Therefore, ? ? > ? ? for infinitely many values of ?, hence ? is not ? ? 21
