COMS 4236

Introduction to Computational Complexity

Introduction

Many computational problems (such as multiplying two numbers, or sorting a list of numbers) are known to be "easy" in the sense that we have efficient algorithms for them. Unfortunately, many other computational problems of great practical importance (such as factoring large numbers, or finding the shortest tour that passes through all the cities on a map) seem to be difficult, in the sense that no efficient algorithms are known. Are these problems really inherently difficult -- do no efficient algorithms exist? -- or do we just need to come up with cleverer algorithms that can solve these problems efficiently?

Questions such as these lie at the heart of computational complexity, which is the study of the fundamental abilities and limitations of efficient computation. Computational complexity is one of the most fundamental and important topics in computer science; indeed, the core question of computational complexity theory ("does P equal NP?") is one of the most famous and important open questions in all of computer science and mathematics.

General Information

Instructor: Rocco Servedio

Instruction modality: On campus, in Mudd 1127; note though that (as with all Spring 2022 courses) the first two weeks of class will be online-only (you can access the lectures through the Zoom link on the Courseworks page). Note also that throughout the semester lectures will be recorded and recordings will be made available to all enrolled students through Courseworks.

Time: Tu/Th 8:40am-9:55am Eastern Time

Course email (for administrative issues; use Ed Discussion for subject matter questions): coms4236columbias22 at gmail dot com

List of Topics

This is a preliminary list of core topics. Other topics may be covered depending on how the semester progresses. Most topics will take several lectures. For more information, click on the "Lectures" tab above.

• Intro to topic; computational problems; Turing Machines; time complexity and P; nondeterminism and NP; Cook-Levin theorem and NP completeness. Note: Coming into the class, you are expected to be familiar with the basics of Turing Machines, nondeterminism, and NP completeness, at the level of Chapters 3 and 7 of the Sipser textbook.
• Oracles and the polynomial time hierarchy
• Hierarchy theorems, basic reslationships among resources
• Space classes (PSPACE, L, NL)
• Randomness as a computational resource, associated complexity classes
• Complexity of counting (exact and approximate)
• Communication complexity
• Circuit complexity: circuits, formulas, lower bounds for constant-depth circuits
• Interactive proofs, IP=PSPACE, Probabilistically checkable proofs (PCP), and inapproximability