Best source: Michael Sipser, Introduction to the Theory of Computation, Chapter 7 (Time Complexity) (not free, check your library or university access). This single chapter covers P, NP, NP-completeness, and reductions at exactly the depth you need (SOLID, not research-level). It's the standard textbook reference, extremely well-written, and you don't need Arora & Barak's heavier Computational Complexity: A Modern Approach for this pass, that book is genuinely research-level and belongs to your deferred Tier 4 material (PCP theorem, IOP formalism), not this foundational section.
Free alternative: MIT OCW 6.045J: Automata, Computability, and Complexity covers P, NP, NP-completeness, and reductions at the same SOLID depth, fully free.
The general concept of a well-defined computational procedure. Worth being precise here specifically because ZK has two algorithms that matter constantly and get compared: the prover's algorithm (expensive, does the real work) and the verifier's algorithm (must stay cheap — this asymmetry is the entire point of a SNARK).
The language every complexity claim in every ZK paper is written in. You'll see this constantly: "prover time O(n log n)," "verifier time O(log n)," "proof size O(1)." Fluency here isn't optional — it's literally how performance claims are communicated in this field.
Typical for witness generation (evaluating a circuit with n gates takes O(n) work) and for a prover's minimum baseline cost — you generally can't do better than linear time if you have to touch every gate at least once.
The gold standard for verifier time and proof size in a well-designed succinct proof system. Merkle authentication paths are O(log n) (from your Graph Theory notes). Many SNARKs achieve O(log n) or even O(1) verification — this is precisely the "succinct" in zk-SNARK.
The single most common prover-side complexity class in modern ZK systems, almost entirely because of FFT/NTT. Most STARK and PLONK-family provers report O(n log n) proving time specifically because their bottleneck operation is a handful of FFTs over the circuit/trace size.
Formally, this is the standard definition of "efficiently computable" / "feasible" in complexity theory — an algorithm running in O(n^k) for some constant k. Both P and NP are defined relative to this notion. This is the formal backbone behind every "PPT" (probabilistic polynomial time) reference in a security definition — an adversary or algorithm is only considered "efficient" if it runs in polynomial time.
Growth like O(2ⁿ) — computationally infeasible for even moderately large n. This is precisely what a SNARK lets the verifier avoid: for many interesting NP statements, finding a witness might require exponential-time search in the worst case, but the SNARK lets the verifier confirm a witness exists in polynomial (often logarithmic) time, without ever performing that expensive search themselves.
The class of problems solvable in polynomial time. This is the complexity class an honest verifier's algorithm must live in — verification needs to be efficient, full stop, or the proof system isn't useful in practice.
The class of problems whose solutions (witnesses) can be verified in polynomial time, even if finding a solution might be much harder. This is not incidental background — this is literally the formal definition connecting to your earlier NP-relation notes: a SNARK proves membership in an NP language, exploiting exactly this "easy to verify, possibly hard to find" asymmetry.
A problem at least as hard as every problem in NP (every NP problem can be reduced to it), but not necessarily itself in NP (verification of a solution might not even be efficient). Worth knowing this distinction exists so you don't conflate NP-hard with NP-complete.
A problem that is both in NP and NP-hard — the "hardest" problems within NP itself, and every NP problem can be efficiently reduced to it. Circuit satisfiability is the canonical NP-complete problem, and this is exactly why it's the target language SNARKs compile down to: since every NP statement can be efficiently reduced to circuit-SAT, having an efficient proof system for circuit-SAT gives you, for free, an efficient proof system for any NP statement.
A transformation from one problem to another, such that solving the target problem solves the original. Two direct, load-bearing uses of this concept in your work:
- Compiling a program into R1CS is a reduction — you're transforming an arbitrary computation (an NP statement) into circuit satisfiability, exploiting NP-completeness of circuit-SAT.
- Security proofs use reductions in the opposite conceptual direction: "if you could break this SNARK's soundness, you could solve [hard problem]" — this is the exact contradiction/reduction structure from your Proof by Contradiction notes, now formally named.
Complexity measured in field operations (additions, multiplications in 𝔽_p) rather than raw bit operations. This is the natural complexity measure for prover algorithms — when a paper says "the prover performs O(n) field multiplications," this is arithmetic complexity, and it's usually the more meaningful measure for ZK performance analysis than bit-level complexity, since field operations are the atomic unit of cost in a prover.
Complexity measured via circuit size (number of gates) and circuit depth (longest path, from your Graph Theory notes) — directly the practical measure of "how expensive is this computation to prove." Circuit complexity theory (as a research area) also studies fundamental limits — which functions require large or deep circuits — relevant background if you ever need to reason about why some computations are inherently expensive to prove in ZK, regardless of which proving system you use.
How many bits must be exchanged between two parties to solve a problem jointly. Directly relevant to interactive proof systems: the total communication between prover and verifier across all rounds is a real, measurable quantity, and minimizing it is part of what "succinct" means. This concept is foundational background for understanding Interactive Oracle Proofs (IOPs) — your upcoming §12 deep-dive — where the "oracle" framing is specifically about managing what the verifier needs to see versus can just spot-check, a communication-complexity-flavored design choice.
You're ready to move on once you can, without notes:
- Explain why circuit satisfiability being NP-complete is the reason R1CS/QAP-based SNARKs can handle "any" NP statement
- Explain the two distinct uses of "reduction" in your own work — one in circuit compilation, one in security proofs — and how they differ
- Explain why O(n log n) shows up so often specifically as prover complexity, connecting it back to FFT
- Explain the practical difference between "P" (verifier's world) and "NP" (what the prover is proving membership in), in your own words