CSCI3360
Introduction to Computational Complexity
Models of computation, nondeterminism and reductions, space complexity, randomized computation, circuits and counting, the polynomial hierarchy, interactive and probabilistically checkable proofs.
Your progress
0/ 33 sections marked complete
Next section: Randomized computation and amplification
Completion marks are saved in this browser.
This course in the web
In the CSCI3360 notes
- Theorem cards
- 94
- Definitions
- 50
- Counterexamples
- 33
- Concept lenses
- 17
- Histories of ideas
- 1
- Proof X-rays
- 33
Sections with a history of an idea
None of these is on the timeline yet.
No concept lens from this course is recorded in the web yet.
Counts cover the 33 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.
In the webTheorem cards 94 · Definitions 50 · Counterexamples 33 · Concept lenses 17 · Histories of ideas 1 · Proof X-rays 33
None of these is on the timeline yet.
No concept lens from this course is recorded in the web yet.
Counts cover the 33 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.
Chapter 1 · 4 sections
Randomized complexity
Fair random bits, RP, BPP, amplification, zero-error computation and identity testing
Theorems 10 · Definitions 4Counterexamples 4Lenses 1Proof X-rays 4
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 1.1
Randomized computation and amplification
Define one-sided and two-sided error and prove majority amplification using independent repetitions.
- 1.2
Zero-error randomized computation
Prove the zero-error characterization using bounded cutoffs and independent one-sided procedures.
- 1.3
Variance bounds and randomized identity tests
Prove a variance amplification bound and analyze a fair-bit polynomial identity test.
- 1.4
Affine hashing and limited independence
Prove pairwise independence over a prime field and distinguish hash-value independence from independence of collision events.
Chapter 2 · 4 sections
Nondeterminism and reductions
NP and coNP certificates, polynomial reductions and a 3-SAT to CLIQUE proof.
Theorems 10 · Definitions 11Counterexamples 5Lenses 3Proof X-rays 4
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 2.1
Nondeterminism, reductions, and completeness
Distinguish NP and coNP certificates and prove a graph reduction, taking 3-SAT hardness as background.
- 2.2
Turning a verifier into a satisfiability instance
Build a Boolean circuit for a bounded computation and prove that circuit satisfiability is NP-complete.
- 2.3
Gate constraints, SAT and three-literal clauses
Preserve circuit sharing with auxiliary variables and prove satisfiability reductions with both directions and size bounds.
- 2.4
Witness search, decision and the class DP
Recover polynomial witnesses from decision queries and combine NP and coNP conditions carefully.
Chapter 3 · 7 sections
Space and reachability
Space models, directed reachability and configuration counting.
Theorems 21 · Definitions 14Counterexamples 7Lenses 4Proof X-rays 7
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 3.1
Space and directed reachability
Define log-space computation, show reachability is in NL and prove NL is contained in P.
- 3.2
Savitch's theorem: simulating nondeterministic space
Prove the general quadratic-space simulation using implicit configuration graphs, and explain polynomial-space equality and reduction composition.
- 3.3
Quantified formulas, space, and interactive proofs
Prove TQBF is PSPACE-complete and that interactive proofs have a polynomial-space upper bound.
- 3.4
Reachability completeness and midpoint recursion
Construct configuration-graph reductions and analyze deterministic midpoint recursion.
- 3.5
Why nondeterministic logspace is closed under complement
Use inductive counting to certify nonreachability in logarithmic space.
- 3.6
2-SAT, implication graphs, and NL-completeness
Prove the implication-graph criterion and connect two-literal satisfiability to logarithmic-space reachability.
- 3.7
The deterministic space hierarchy
Use configuration bounds and bounded simulation to prove that more space decides strictly more languages.
Chapter 4 · 4 sections
Computation and models
Decision problems, resource bounds, encoding and undecidability.
Theorems 10 · Definitions 5Counterexamples 4Lenses 1History 1Proof X-rays 4
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 4.1
Computation, resources, and diagonalization
Define computational resources and use counting and diagonalization to study decidability.
- 4.2
Simulating several tapes with one tape
Prove polynomial machine-model robustness by keeping separate old and new head markers.
- 4.3
The deterministic time hierarchy
Use a clocked universal simulation and diagonalization to separate deterministic time bounds.
- 4.4
Oracle worlds and the limits of relativization
Construct oracle settings with opposite P-versus-NP outcomes and track which queries a diagonalization must protect.
Chapter 5 · 3 sections
Counting and circuits
Witness counting and polynomial-size nonuniform circuits.
Theorems 9 · Definitions 1Counterexamples 3Lenses 1Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 5.1
Counting witnesses and nonuniform circuits
Study #P witness counts and nonuniform circuit families.
- 5.2
Majority acceptance and counting
Define PP by exact majority, relate it to witness counting, and prove elementary containments and complement closure.
- 5.3
Parsimonious reductions and the permanent
Preserve witness counts through Boolean gates, interpret the permanent, and compute its parity.
Chapter 6 · 1 section
Probability bounds
A Bernoulli exponential-tail derivation.
Theorems 3 · Definitions 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 6.1
An exponential tail bound for Bernoulli trials
Derive the Bernoulli-indicator concentration bound and majority amplification.
Chapter 7 · 1 section
Randomized computation and advice
Revisit randomized error amplification and prove a nonuniform fixed-tape consequence using the union bound.
Theorems 3 · Definitions 2Counterexamples 2Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 7.1
Error amplification and fixed randomness
Revisit randomized error amplification and prove a nonuniform fixed-tape consequence using the union bound.
Chapter 8 · 4 sections
Alternation and the polynomial hierarchy
Alternation and the polynomial hierarchy
Theorems 11 · Definitions 4Counterexamples 4Lenses 3Proof X-rays 4
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 8.1
Alternation and the polynomial hierarchy
Build quantified verifier classes and see how complement and nesting change the quantifiers.
- 8.2
Complete quantified formulas at each hierarchy level
Encode polynomial-time predicates as formulas without adding an alternation.
- 8.3
Small circuits and the polynomial hierarchy
Prove the Karp–Lipton collapse using nonuniform witness search and explicit quantifiers.
- 8.4
Circuit advice and hierarchy collapse
Relate nonuniform advice to circuits, count small circuits, and prove a conditional hierarchy collapse.
Chapter 9 · 4 sections
Interactive proofs
Interactive proofs
Theorems 13 · Definitions 6Counterexamples 2Lenses 2Proof X-rays 4
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 9.1
Interactive proofs and graph nonisomorphism
Define completeness and soundness in an interactive proof and analyze the graph nonisomorphism protocol.
- 9.2
The sum-check protocol
Verify a claimed finite-field sum with interactive low-degree checks and an adaptive soundness proof.
- 9.3
From polynomial space to interactive proofs
Use multilinear matrix extensions and sum-check to prove PSPACE is contained in IP.
- 9.4
Merlin, Arthur, and public randomness
Define MA and AM with explicit quantifiers and prove that MA is contained in AM.
Chapter 10 · 1 section
Probabilistically checkable proofs
Probabilistically checkable proofs
Theorems 4 · Definitions 2Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 10.1
Probabilistically checkable proofs and gap reductions
Define random-access proof verification and derive a conditional approximation barrier from a stated gap theorem.