Skip to content

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.

10 chapters · 33 sectionsEN · 繁 · 简
My course notes

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.

Open this course in the knowledge map

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.

Open this course in the knowledge map

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.1

    Randomized computation and amplification

    Define one-sided and two-sided error and prove majority amplification using independent repetitions.

  2. 1.2

    Zero-error randomized computation

    Prove the zero-error characterization using bounded cutoffs and independent one-sided procedures.

  3. 1.3

    Variance bounds and randomized identity tests

    Prove a variance amplification bound and analyze a fair-bit polynomial identity test.

  4. 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

  1. 2.1

    Nondeterminism, reductions, and completeness

    Distinguish NP and coNP certificates and prove a graph reduction, taking 3-SAT hardness as background.

  2. 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.

  3. 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.

  4. 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

  1. 3.1

    Space and directed reachability

    Define log-space computation, show reachability is in NL and prove NL is contained in P.

  2. 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.3

    Quantified formulas, space, and interactive proofs

    Prove TQBF is PSPACE-complete and that interactive proofs have a polynomial-space upper bound.

  4. 3.4

    Reachability completeness and midpoint recursion

    Construct configuration-graph reductions and analyze deterministic midpoint recursion.

  5. 3.5

    Why nondeterministic logspace is closed under complement

    Use inductive counting to certify nonreachability in logarithmic space.

  6. 3.6

    2-SAT, implication graphs, and NL-completeness

    Prove the implication-graph criterion and connect two-literal satisfiability to logarithmic-space reachability.

  7. 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

  1. 4.1

    Computation, resources, and diagonalization

    Define computational resources and use counting and diagonalization to study decidability.

  2. 4.2

    Simulating several tapes with one tape

    Prove polynomial machine-model robustness by keeping separate old and new head markers.

  3. 4.3

    The deterministic time hierarchy

    Use a clocked universal simulation and diagonalization to separate deterministic time bounds.

  4. 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

  1. 5.1

    Counting witnesses and nonuniform circuits

    Study #P witness counts and nonuniform circuit families.

  2. 5.2

    Majority acceptance and counting

    Define PP by exact majority, relate it to witness counting, and prove elementary containments and complement closure.

  3. 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

  1. 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

  1. 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

  1. 8.1

    Alternation and the polynomial hierarchy

    Build quantified verifier classes and see how complement and nesting change the quantifiers.

  2. 8.2

    Complete quantified formulas at each hierarchy level

    Encode polynomial-time predicates as formulas without adding an alternation.

  3. 8.3

    Small circuits and the polynomial hierarchy

    Prove the Karp–Lipton collapse using nonuniform witness search and explicit quantifiers.

  4. 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

  1. 9.1

    Interactive proofs and graph nonisomorphism

    Define completeness and soundness in an interactive proof and analyze the graph nonisomorphism protocol.

  2. 9.2

    The sum-check protocol

    Verify a claimed finite-field sum with interactive low-degree checks and an adaptive soundness proof.

  3. 9.3

    From polynomial space to interactive proofs

    Use multilinear matrix extensions and sum-check to prove PSPACE is contained in IP.

  4. 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

  1. 10.1

    Probabilistically checkable proofs and gap reductions

    Define random-access proof verification and derive a conditional approximation barrier from a stated gap theorem.

Vercel visit statistics and public-page performance measurements each require separate consent. Neither is needed to use the website.

Website function storage (used when needed)

Security, sign-in and your chosen preferences use storage when needed. This is separate from optional statistics.

Withdrawing stops future statistics. The page reloads if analytics code needs unloading. It does not delete data already sent.

Read Cookie and storage details