Computational Complexity Class Notes
Computational Complexity, by Christos H. Papadimitriou,
Addison-Wesley Publishing (1995)
Copies of the classnotes are on the internet in PDF format as given below. The "Proofs of Theorems" files were prepared in Beamer. The "Printout of Proofs" are printable PDF files of the Beamer slides without the pauses. These notes and supplements have not been classroom tested (and so may have some typographical errors).
Computational Complxity is not a formal class at ETSU. These notes are meant for self-study and reference.
Classes which cover similar topics are offered by the Department of Computer Science (these class descriptions are from the ETSU 2022-23 Graduate Catalog):
- Formal Languages and Computational Complexity (CSCI 5610). Prerequisites: MATH 2710, CSCI 2210 or consent of the instructor.
Problem-solving is a fundamental aspect of computer science. This course teaches students how to reduce a computational problem to its simplest form and analyze the problem to determine its inherent computational complexity. Topics include formal languages and automata theory, Turing machines, computational complexity, and the theory of NP-completeness.
When Offered: Variable.
- Analysis Of Algorithms (CSCI 5620).
Prerequisites: Differential and integral calculus, discrete structures, data structures.
This course covers basic techniques for analyzing algorithmic complexity. It describes the design and analysis of selected algorithms for solving important problems that arise often in applications of computer science, including sorting, selection, graph theory problems (e.g., shortest path, graph traversals), string matching, dynamic programming problems, NP-complete problems. When Offered: Fall, alternate years [odd falls].
The first of these CSCI classes is most similar to the material presented here. However, Formal Languages and Computational Complexity (CSCI 5610) only has prerequisites of Discrete Structures (MATH 2710) or Data Structures (CSCI 2210).
Discrete Structures (MATH 2710) was discontinued in the ealy 2000s, though I have online notes for Discrete Structures from the last time I taught it (spring 2001). For the notes presented here, prerequisite material would include Mathematical Reasoning (MATH 3000) and Introduction to Set Theory (not a formal ETSU class; some of this material is covered in Mathematical Reasoning, but not deeply). Some exposure to graph theory is desirable, since several of the initial problems encountered here involve graph theory problems. A sufficient background is given by Introduction to Graph Theory (MATH 4347/5347).
Copies of the classnotes are on the internet in PDF format as given below. The "Proofs of Theorems" files were prepared in Beamer. The "Printout of Proofs" are printable PDF files of the Beamer slides without the pauses. These notes and supplements have not been classroom tested (and so may have some typographical errors).
Preface.
PART I: ALGORITHMS
Chapter 1. Problems and Algorithms.
- Section 1.1. Graph Reachability. Section 1.1 notes
- Section 1.2. Maximum Flow and Matching.
- Section 1.3. The Traveling Salesman Problem.
- Section 1.4. Notes, References, and Problems.
- Study Guide 1.
Chapter 2. Turing Machines.
- Section 2.1. Turing Machine Basics. Section 2.1 notes
- Section 2.2. Turing Machines as Algorithms.
- Section 2.3. Turing Machines with Multiple Strings.
- Section 2.4. Linear Speedup.
- Section 2.5. Space Bounds.
- Section 2.6. Random Access Machines.
- Section 2.7. Nondeterministic Machines.
- Section 2.8. Notes, References, and Problems.
- Study Guide 2.
Chapter 3. Computability.
- Section 3.1. Universal Turing Machines.
- Section 3.2. The Halting Problem.
- Section 3.3. More Undecidability.
- Section 3.4. Notes, References, and Problems.
- Study Guide 3.
PART II: LOGIC
Chapter 4. Boolean Logic.
- Section 4.1. Boolean Expressions. (partial) Section 4.1 notes
- Section 4.2. Satisfiability and Validity.
- Section 4.3. Boolean Functions and Circuits.
- Section 4.4. Notes, References, and Problems.
- Study Guide 4.
Chapter 5. First-Order Logic.
- Section 5.1. The Syntax of First-Order Logic.
- Section 5.2. Models.
- Section 5.3. Valid Expressions.
- Section 5.4. Axioms and Proofs.
- Section 5.5. The Completeness Theorem.
- Section 5.6. Consequences of the Completeness Theorem.
- Section 5.7. Second-Order Logic.
- Section 5.8. Notes, References, and Problems.
- Study Guide 5.
Chapter 6. Undecidability in Logic.
- Section 6.1. Axioms of Number Theorem.
- Section 6.2. Complexity as a Number-Theoretic Concept.
- Section 6.3. Undecidability and Incompleteness.
- Section 6.4. Notes, References, and Problems.
- Study Guide 6.
PART III: P AND NP
Chapter 7. Relations Between Complexity Classes.
Chapter 8. Reductions and Completeness.
Chapter 9. NP-Complete Problems.
Chapter 10. coNP and Function Problems.
Chapter 11. Randomized Computation.
Chapter 12. Cryptography.
Chapter 13. Approximability.
Chapter 14. On P vs. NP.
PART IV: INSIDE P
Chapter 15. Parallel Computation.
Chapter 16. Logarithmic Space.
PART V: BEYOND NP
Chapter 17. The Polynomial Hierarchy.
Chapter 18. Comutation that Counts.
Chapter 19. Polynomial Space.
Chapter 20. A Glimpse Beyond.
Return to Bob Gardner's home page