Theory of Computation

COSC 39, Spring 2025

Main | Schedule | Homeworks | About

Course Schedule

Introduction

3/31

administrivia; what is the purpose of this course? knowledge, skill, philosophy

• Useful resources for reviewing prerequisites:
  • Background knowledge: Sipser Chapter 0
  • Induction: Erickson lecture 1, Appendix I
• Train your thinking and communication skills in math:
  • There’s more to mathematics than rigour and proofs by Terence Tao; here's a video if you prefer him talking in person
  • On writing by Terence Tao
  • Notes on mathematical writing by Clark Barwick
  • Algorithm is not a four-letter word by Jamis Buck
• Universal computation and our mind:
  • Quantum Computing since Democritus by Scott Aaronson. Entertaining, crisp, and original. Try to get a copy from the library.
  • A Turing test for free will by Seth Lloyd
  • What Can Theoretical Computer Science Contribute to the Discussion of Consciousness by Lenore, Manuel, and Avrim Blum
• Why this course?
  • What is the enlightenment I'm supposed to attain after studying finite automata?
  • How practical is Automata Theory?

Languages and Machine Models

4/2

languages, problems, and encoding; regular expressions [scribbles]

• Erickson lecture 2.1–2.3, Sipser Chapter 1.3 regular expressions

4/3

constructing regular expressions [worksheet]

4/4

finite automata and automatic languages: machines with registers [scribbles]

• Erickson lecture 3.1–3.5, Sipser Chapter 1.1

4/7

DFA constructions [worksheet]

Nondeterminism

4/9

regular languages are automatic: nondeterministic finite automata [scribbles]

• Erickson lecture 4.1–4.3, 4.6–4.7, Sipser Chapter 1.2, 1.3 (Theorem 1.54)

4/10

construting NFAs [worksheet]

4/11

power of nondeterminism: closure properties of NFAs [scribbles]

4/14

language transformations and closure properties [worksheet]

Beyond Regularity

4/16

Kleene theorem: where multiple models coincide [scribbles]

• Erickson lecture 4.4–4.5, 4.8–4.9, Sipser Chapter 1.2 (Theorem 1.39), 1.3 (Lemma 1.60)

4/17

constructing regular expressions for language complement [worksheet]

4/18

limits of regularity: fooling sets and Myhill-Nerode theorem; examples of nonregular languages [scribbles]

• Erickson lecture 3.8–3.9

4/21

fooling set constructions [worksheet]

Turing Machines and Decidability

4/23

Turing machine: it's just CPU with memory [scribbles]

• Erickson lecture 6.1–6.7, Sipser Chapter 3
• The Wikipedia page for the Church–Turing thesis is surprisingly detailed
• Things equivalent to Turing machines:
  • Baba Is You
  • Game of Life
  • Magic: The Gathering
  • Powerpoint (Tom Wildenhain is the only person qualified to put Powerpoint under Programming Languages section in his CV.)
  • Minecraft (not surprisingly; but look at its spec/speed!)
  • One single x86 instruction (All the other instructions are fluff! ... and of course, somebody use it to run Doom)
  • ... and many more
• Inception:
  • Game of Life

4/24

Equivalence between different computing devices [worksheet]

4/25

Church-Turing thesis: CPU with memory is universal computation; universality implies incomputability (oh the irony) [scribbles]

• Erickson lecture 6.8, 7.5–7.8, Sipser Chapter 4, QCD Chapter 3
• Can you write a program that output the source code of itself?
  • Wikipedia page on Quine
  • Quines (self-replicating programs)
• On halting problem and imcompleteness theorems
  • Rosser’s Theorem via Turing machines
  • The Surprise Examination Paradox and the Second Incompleteness Theorem

4/28

Is my pseudocode safe? [worksheet]

Resources and Verification

4/30

Time complexity, verification and nondeterminism, P vs NP [scribbles]

• Erickson chapter 12.1–12.2, Sipser Chapter 7.1–7.3, QCD Chapter 6

5/1

Classifying problems [worksheet]

5/2

NP-hardness and Cook-Levin theorem: no pursuit is useless; mapping and oracle reductions [scribbles]

• Erickson chapter 12.3–12.6, Sipser Chapter 7.4, QCD Chapter 6
• The notion of self-reducibility was important near the dawn of complexity theory, and gave rise to many interesting theorems and techiniques. These are mostly out-of-scope for CS39 but in case you are interested.
  • The Power of Self-Reducibility: Selectivity, Information, and Approximation, by Lane A. Hemaspaandra
  • The Self-Reducibility Technique

5/5

Self-reductions [worksheet]

Reductions

5/7

NP-hardness reductions [scribbles]

• Erickson chapter 12.6–12.11, Sipser Chapter 7.5
• There are so much resourses online about NP-hardness I can't even. But here's a few that I find extra helpful:
  • Lecture by Erik Demaine from MIT, including a proof that Super Mario Bros. is NP-hard (and a few other problems we didn't cover in class).
  • P vs. NP and the Computational Complexity Zoo
  • SIGBOVIK 2007: Generalized Super Mario Bros. is NP-Complete. Super Mario BROOOOOOS.

5/8

NP-hardness reductions between similar problems [worksheet]

5/9

Exponential-time hypotheses: No, I mean they are really really hard [scribbles]

• Algorithmic Lower Bounds: Fun with Hardness Proofs by Erik Demaine
• (Strong) Exponential Time Hypothesis
• The (S)ETH and Implications by Michael Lampis, Feb 2, 2021
• Fine-grained complexity:
  • Fine-Grained Algorithms and Complexity by the Williams at MIT. A full semester course on fine-grained complexity.
  • Fine-Grained Complexity and Algorithm Design, held between Aug 19 – Dec 18, 2015 at Simons Institute. Lots of good talks!
  • On some fine-grained questions in algorithms and complexity by Virginia Vassilevska Williams
  • Hypotheses about Satisfiability and their Consequences by Russell Impagliazzo (Yes, the one who came up with ETH and SETH), streamed on Feb 11, 2021

5/12

(S)ETH reductions [worksheet; merged with Homework 6]

5/14

NP-hardness reductions: How to pick the right left problem [scribbles]

• Erickson chapter 12.12–12.13, Sipser Chapter 7.5
• Three-dimensional matching is NP-Hard, by Shrinu Kushagra

5/15

NP-hardness reductions by gadget construction [worksheet]

Advanced topics

Randomness

5/16

Randomized algorithm, BPP, and error reduction; polynomial identity testing [scribbles]

• References for randomized algorithm:
  • Randomized Algorithms by Luca Trevisan, Lecture 12
  • Randomized Algorithms by Motwani and Raghavan, Chapter 7.1–7.6

5/19

Fingerprinting

Communication

5/21

Why can't we just solve NP-hard problems using LLM?

5/22

[TBD]

5/23

Quantum computing: we are not performing computing in parallel universes exponentially faster

5/26

[TBD]

Onward!

5/28

Interactive proof for #P; Cryptography: one-time pad and commitment scheme; Zero-knowledge proofs and secure computations

• Theoretical Cryptography, Lecture 1 by Manuel Blum
• A Personal View of Average-Case Complexity by Russell Impagliazzo, 1995
• Zero-knowledge proofs:
  • Zero Knowledge Proof: ELI5 (Halloween Ed.) by Hackernoon
  • Zero Knowledge Proof by Numberphile

5/29

Fun with zero-knowledge proofs

5/30

How does new discovery (like quantum physics and time travel) change our perspective of computation?

• Quantum Computing Since Democritus, Lecture 19: Time Travel by Scott Aaronson
• Harry Potter and the Methods of Rationality, Chapter 17 by Eliezer Yudkowsky, 2010–2015
• Closed Timelike Curves Make Quantum and Classical Computing Equivalent by Scott Aaronson and John Watrous, 2008
• Quantum Computing
  • Quantum Computing Since Democritus, Lecture 9–10 by Scott Aaronson
  • Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak, Chapter 20
  • A visit from Alice and Bob by Henry Yuen; an amusing story about the breakthrough result MIP* = RE
  • The shape of MIP* = RE by Henry Yuen

6/2

[TBD]