Mathematical Introduction
The first part of the course will cover the mathematical fundamentals that are crucial for understanding complexity. We will address:
• Proof techniques: A review of basic proof methods, focusing on what students have learned in Discrete Structures.
• Representation of data, problems, and languages: How to formally model computational problems mathematically.
• Bijections: The importance of bijective mappings in the context of comparing the sizes of sets.
• Diagonalization: A powerful tool for proving the existence of uncomputable and more complex problems.
Introduction to Computational Models (Automata)
We will explore the initial abstract models of computation that serve as the foundation for understanding more complex models. The content includes:
• Automata and their equivalences: Deterministic and non-deterministic finite automata.
• Regular expressions (RE): The connection between automata and formal languages.
• The Pumping Lemma: A method for proving that certain languages are not regular.
• The Myhill-Nerode theorem: A key theorem for minimizing automata.
The General Model of Computation and Uncomputability
This section will introduce the universal model of computation and its inherent limitations. We will cover:
• The Turing Machine (TM) and its variations: The universal model of computation and its robustness.
• The Universal Turing Machine: A concept that allows for the simulation of any arbitrary Turing machine.
• Uncomputability: The existence of problems for which no algorithm can be found.
• Reductions: The fundamental mechanism for proving that problems are related to one another.
• Rice's Theorem: An important theorem on the uncomputability of non-trivial properties of Turing machine languages.
Complexity
In the final part, we will focus on classifying problems based on their computational difficulty. The content includes:
• Deterministic and non-deterministic complexity classes: The class P as a collection of "easy" problems and the class NP as a collection of "harder" problems.
• P and NP (and PSPACE): An in-depth analysis of these classes, including Savitch's theorem, which relates deterministic and non-deterministic space.
• Karp reductions: Techniques for proving that a problem is NP-complete.
• The Cook-Levin theorem: The foundational theorem that proves the satisfiability problem (SAT) is NP-complete.
• Examples of NP-complete problems: We will discuss classic examples such as satisfiability (SAT), cliques, graph coloring, subset-sum, Hamiltonian cycle (HC), and others.
