Table of Contents

Motivation

For the last six months, I’ve been doing research on SAT solvers. More specifically, model counting. I’m a math major, so naturally I thought “let’s count things” sounded like a good summer project. The question was simple: does the phase transition phenomenon (where SAT instances go from easy to hard to easy again as you increase constraints) extend to counting solutions?

Quick primer: the #SAT problem asks “given a Boolean formula $\phi$, how many assignments make it true?” It’s #P-complete, which means it’s at least as hard as NP-complete problems, probably harder.

Yes, the phase transition extends to counting. Paper coming soon.

But here’s what happened while I was running experiments. I kept measuring different things without realizing they were different. Circuit size would explode at one density. Solver runtime would spike somewhere else. The number of random XOR constraints needed would climb in a third region. And I’d think “okay, the problem is getting complex here,” without being precise about what “complex” meant.

Then PhD application season hit. I started reading papers from professors I wanted to work with. One paper would talk about “proof complexity lower bounds.” Another about “circuit complexity barriers.” A third about “communication complexity of distributed protocols.” And I realized something annoying: they were all using the word “complexity” to mean completely different things. [I know this sounds obvious, but it hadn’t clicked before how broad compexlity is.]

Time complexity (how long does it take) is different from circuit complexity (how many gates do you need). Both are different from query complexity (how many input bits must you read). All three are different from proof complexity (how long is the certificate). And none of them are Kolmogorov complexity (how compressible is this object).

Wait, what?

This post is me trying to make sense of that mess. Not comprehensively (that would take a textbook I’m not qualified to write), but enough so that when someone says “oh that’s communication-complex” or “the query complexity is too high,” you’ll know what lens they’re using to measure hardness.

Because here’s the thing: when I was measuring #SAT difficulty this summer, I was simultaneously measuring like five different complexity types without realizing it. They all spiked at roughly the same place (the phase transition), but for different structural reasons. Understanding why requires knowing what each complexity measure actually captures.

So let’s map the zoo.

Time & Space

Let’s start with the classics, the ones everyone learns first.

Time complexity: how many steps does the algorithm take? Space complexity: how much memory does it use?

For a Turing machine solving problem $A$, time complexity $T(n)$ is the maximum number of steps on any input of length $n$. Space complexity $S(n)$ is the maximum number of tape cells used. Both are measured in the worst case (usually).

This gives us the standard hierarchy. P is polynomial time (the “tractable” class). NP is nondeterministic polynomial time (or equivalently, polynomial-time verifiable). PSPACE is polynomial space. And so on.

For #SAT (counting satisfying assignments), we know it’s #P-complete. This means it’s at least as hard as any NP problem, probably harder. Toda’s Theorem tells us the entire polynomial hierarchy collapses to $\text{P}^{\#\text{P}}$ (if you can count, you can solve anything in PH). Counting is powerful.

But time complexity doesn’t tell you why something is hard. It just says “this takes a long time.” When my #SAT solver was slow at the phase transition, time complexity told me “yep, it’s slow,” but not what structural property of the formula caused that slowness.

For that, I needed different lenses.

Circuit Complexity

When I compiled CNF formulas to d-DNNF (decision diagrams for model counting), I was measuring circuit complexity: how many logical gates (AND, OR, NOT) does it take to represent this Boolean function?

Two main measures exist here. Size is the total number of gates. Depth is the longest path from input to output (this measures parallelizability).

Classes like NC (polylog depth, polynomial size) capture “efficiently parallelizable” problems. AC$^0$ is constant-depth circuits with unbounded fan-in. P/poly is polynomial-size circuits, the most general non-uniform class.

Here’s the interesting part: we can’t prove any superlinear lower bounds for explicit functions. Shannon proved in 1949 that most functions need exponential circuits (by counting), but we can’t point to a specific function and prove it needs more than $O(n)$ gates. The best result is Ryan Williams’ 2011 breakthrough: NEXP is not in ACC$^0$ (circuits with modular counting gates).

That’s it. That’s all we have. We think 3SAT needs exponential circuits, but we can’t prove it. If we could, P would not equal NP.

For my #SAT experiments, the compiled circuits exploded in size at the phase transition. Why? Because the solution space fragments. The circuit has to branch on many variables before determining satisfiability. The formula has high “treewidth” (a graph measure of branching structure). This structural complexity causes the circuit blow-up.

But size isn’t the only way to think about accessing information.

Query Complexity

Query complexity (also called decision tree complexity) asks a purer question: ignoring computation entirely, how many input bits must you examine to compute the answer?

Model: you have input $x \in {0,1}^n$. You can query “what is $x_i$?” The deterministic query complexity $D(f)$ is the minimum number of queries needed in the worst case to determine $f(x)$. There are also randomized ($R(f)$) and quantum ($Q(f)$) versions.

Example: the OR function (is there a 1 in the input?). Deterministically, you need $D(\text{OR}) = n$ queries because the 1 might be in the last position you check. But Grover’s algorithm gives $Q(\text{OR}) = O(\sqrt{n})$ with a quantum computer. This quadratic speedup is the canonical quantum search advantage.

Another example: sorting $n$ items requires $\Omega(n \log n)$ comparisons in the comparison model. This is a query complexity lower bound (each comparison is a query), and it immediately implies that no comparison-based sorting algorithm can be faster than $O(n \log n)$.

Now, how does this relate to #SAT? Strictly speaking, my XOR-constraint approach isn’t classical query complexity (which queries input bits). Instead, it’s more like sampling complexity or solution space probing: we’re adding random XOR constraints and observing how the solution count changes. Each XOR constraint gives us one “query” into the structure of the solution space. The number of constraints needed to get an $(\epsilon, \delta)$-approximation is, in spirit, a query-like measure.

At the phase transition, we need more XOR constraints because the solution distribution is neither uniform nor sparse. It’s structured in this weird fragmented way that requires more samples to characterize accurately.

One of my favorite results in query complexity is Hao Huang’s 2019 proof of the Sensitivity Conjecture. Sensitivity $s(f)$ measures how many bits you can flip in an input to change the output. Block sensitivity $bs(f)$ is similar but for blocks of bits. For 25 years, people wondered if $bs(f)$ was polynomially bounded by $s(f)$. Huang proved $bs(f) \leq s(f)^4$ with a two-page argument using spectral graph theory and the Cauchy Interlace Theorem.

Two pages. 25-year-old problem. That’s the kind of math that makes you spill coffee.

Proof Complexity

Here’s where things get weird. Proof complexity asks: how many steps does it take to prove something is unsatisfiable?

Most modern SAT solvers use CDCL (Conflict-Driven Clause Learning), which is essentially doing Resolution: a proof system where you derive new clauses from existing ones.

Rule: from clauses $(A \vee x)$ and $(B \vee \neg x)$, derive $(A \vee B)$.

To prove a CNF is unsatisfiable, derive the empty clause (contradiction). The proof complexity is the number of clauses in the shortest derivation.

Haken’s 1985 result: the Pigeonhole Principle ($n+1$ pigeons in $n$ holes) requires exponential-size Resolution proofs. This means CDCL solvers must take exponential time on these formulas. The hardness isn’t in the problem (easy to state), it’s in the structure of reasoning required.

For random 3-CNF at the critical density, Resolution proofs are also hard. The unsatisfiable core is hidden deep. You can’t find a small, easily refutable subformula. The refutation requires reasoning about many clauses simultaneously, leading to exponential blow-up.

Ben-Sasson and Wigderson formalized this with the width-size tradeoff: if a Resolution proof has small width (short clauses), then it’s short. But if every proof requires wide clauses (mentioning many variables), then every proof is long. Random 3-CNF at the critical density has high proof width, hence high proof complexity, hence hard for CDCL.

This is a different kind of hardness than “the circuit is big” or “you need many queries.” It’s about the logical certificates themselves.

And here’s the kicker: Cook-Reckhow (1979) proved that if there exists a proof system where every tautology has polynomial-size proofs, then $\text{NP} = \text{coNP}$. So proving lower bounds for increasingly strong proof systems is a path toward separating complexity classes. We’ve done it for Resolution, Cutting Planes, bounded-depth Frege. For general Frege (standard propositional logic)? Still open.

Kolmogorov Complexity

Okay, curveball time. Kolmogorov complexity measures something completely different: information content, independent of computation time.

Definition: $K(x)$ is the length of the shortest program that outputs $x$. Random strings have $K(x) \approx |x|$ (incompressible). Structured strings like “0000…0” have low $K(x)$ (program is “print ‘0’ $n$ times”).

This is uncomputable. You can’t write an algorithm that takes $x$ and outputs $K(x)$. Proof: Berry’s paradox (“the smallest number not definable in under sixty characters” defines itself in under sixty characters, contradiction).

Why does this matter for SAT? Because time-bounded Kolmogorov complexity connects to cryptography.

Levin’s Kt complexity measures program length plus log runtime:

$$Kt(x) = \min { |p| + \log t \mid U(p) = x \text{ in } t \text{ steps} }$$

Liu and Pass (2020) proved: one-way functions exist if and only if Kt complexity is hard to compute on average. This connects cryptographic hardness to meta-complexity (the complexity of computing complexity).

For SAT at the phase transition, formulas are neither maximally random nor maximally structured. They’re in a weird middle ground where their Kolmogorov complexity is interesting and hard to compute. I’m not saying this directly impacts my experiments (it doesn’t), but it’s a reminder that “complexity” can mean “information content” rather than “computational cost.”

Communication Complexity

What if the input isn’t all in one place?

Communication complexity: Alice has $x$, Bob has $y$, they want to compute $f(x, y)$. They exchange bits. The communication complexity $D(f)$ is the minimum number of bits needed in the worst case.

Example: Equality (is $x = y$?). Any deterministic protocol needs $n$ bits. Essentially, one party sends their entire input. But with randomness, you can do it in $O(\log n)$ bits (hash functions!).

The canonical hard problem is Set Disjointness: Alice has set $A$, Bob has set $B$, are they disjoint? This needs $\Omega(n)$ communication. Proof uses a “fooling set” argument (a set of input pairs forcing the protocol to distinguish them all).

Why does this matter? Because communication lower bounds imply circuit lower bounds. The Karchmer-Wigderson relation connects circuit depth to communication complexity: the depth of a circuit computing $f$ equals the communication complexity of a certain two-party game about $f$. This is how we prove AC$^0$ lower bounds.

For distributed model counting (formula split across machines), communication is the bottleneck. You can’t send the whole formula (too big). You need protocols that minimize communication while getting accurate counts. Active research area.

Algebraic Complexity

Here’s where things get elegant. Algebraic complexity (also called arithmetic complexity) studies computation over fields instead of bits. Instead of Boolean circuits with AND/OR/NOT gates, we have arithmetic circuits with $+, -, \times$ gates over fields like $\mathbb{R}$ or $\mathbb{C}$.

Leslie Valiant defined two classes to mirror P and NP:

VP (Valiant’s P): families of polynomials ${f_n}$ computable by arithmetic circuits of polynomial size and polynomial degree.

Example: The determinant of an $n \times n$ matrix. It’s computable in $O(n^3)$ operations (Gaussian elimination) or $O(\log^2 n)$ depth (Berkowitz’s algorithm). Determinant is in VP.

VNP (Valiant’s NP): polynomials definable as a sum over exponentially many terms, where each term is efficiently computable.

Example: The permanent of a matrix:

$$\text{Perm}(X) = \sum_{\sigma \in S_n} \prod_{i=1}^n x_{i,\sigma(i)}$$

This looks almost identical to the determinant (which has $(-1)^{\text{sgn}(\sigma)}$ terms), but without the sign. Computing permanents is #P-complete in the Boolean world. In the algebraic world, permanent is complete for VNP.

Valiant’s Hypothesis: $\text{VP} \neq \text{VNP}$.

This is the algebraic analog of $\text{P} \neq \text{NP}$. If VP = VNP, then the permanent has polynomial-size arithmetic circuits, which would imply $\text{P}^{\#\text{P}} \subseteq \text{P/poly}$, collapsing the polynomial hierarchy. So algebraically proving VP $\neq$ VNP would be huge.

Why is this “cleaner” than Boolean complexity? Because the algebraic setting has more structure. We can use tools from algebraic geometry, representation theory, and commutative algebra. The Geometric Complexity Theory (GCT) program, launched by Mulmuley and Sohoni, tries to prove VP $\neq$ VNP using representation-theoretic obstructions.

The core idea: frame permanent vs determinant as a question about orbit closures in representation theory. Can the permanent be approximated by a linear projection of a slightly larger determinant? GCT tries to prove “no” by finding representations that appear in the permanent’s orbit but not the determinant’s.

It hasn’t succeeded yet (and recent results show simple “occurrence obstructions” don’t work), but the program drives deep research connecting complexity to algebraic geometry.

For my work, this is tangential. But it’s a reminder that choosing the right mathematical setting matters. Boolean complexity is stuck on lower bounds. Algebraic complexity has more tools available. Sometimes the right lens makes all the difference.

Descriptive Complexity

Completely different angle. Descriptive complexity measures problems by the logical formulas needed to describe them.

Fagin’s Theorem (1974): NP = Existential Second-Order Logic. A problem is in NP iff it’s expressible as “there exists a relation $R$ such that $\phi(R)$ holds” for some first-order $\phi$.

Example: 3-colorability. “There exist three sets of vertices (Red, Green, Blue) such that every vertex is in one set, and no two adjacent vertices share a set.” The existential quantification is the “guessing” in NP. The first-order part is the “verification.”

This extends:

• AC$^0$ = First-Order Logic
• P = First-Order + Least Fixed Point (on ordered structures)
• NP = Existential Second-Order
• PH = Full Second-Order
• PSPACE = First-Order + Partial Fixed Point

So P vs NP becomes: is FO + LFP equal to Existential Second-Order?

This is a question about expressive power of logical languages, not Turing machines. Same question, different lens.

I find this beautiful but not directly useful for experiments. It’s more philosophical: “What kind of logic expresses this problem?” But it’s a reminder that complexity isn’t just about machines. It’s about languages, logic, expressiveness.

Parameterized Complexity

Parameterized complexity refines P vs NP by acknowledging inputs have structure.

Instead of measuring complexity as just $f(n)$, pick a parameter $k$ (solution size, treewidth, number of variables) and ask: is it solvable in $f(k) \cdot \text{poly}(n)$ time?

If yes, it’s Fixed-Parameter Tractable (FPT). Exponential blow-up is confined to $k$, not $n$.

Example: Vertex Cover. Find $k$ vertices covering all edges. Brute force: $O(n^k)$, not FPT. But branching algorithm: pick an edge, one endpoint must be in the cover, branch on both. Recursion depth $k$, each level $O(n)$. Total: $O(2^k \cdot n)$. This is FPT.

For SAT parameterized by treewidth, the problem becomes FPT. Low-treewidth formulas are easier.

At the #SAT phase transition, treewidth explodes. The constraint graph becomes highly interconnected. This is why compilation struggles: dynamic programming over the constraint graph has exponential blow-up with high treewidth.

Parameterized complexity gives vocabulary to say “this problem is hard because this parameter is large.” More fine-grained than P vs NP.

Data vs Expression Complexity

So here is the thing: Dr. Vardi is my undergraduate advisor, and it so happens that I had to read one of papers to lecture for a class he teaches where he talks about another type of complexity. In his 1982 paper “The Complexity of Relational Query Languages,” he made a distinction that should have been obvious but somehow wasn’t standard at the time.

Vardi asked: when we talk about the complexity of a query language, what are we actually measuring?

He split it into two types:

Data complexity: Fix a specific query. How hard is it to evaluate that query as a function of the database size? This measures “how difficult are the individual questions asked in this language?”

Expression complexity: Fix a specific database. How hard is it to evaluate arbitrary queries (represented by expressions in the language) on that database, as a function of the expression size? This measures “how difficult is answering different questions in this language?”

Same query language. Two completely different complexity measures. And they’re not just different by a constant factor. Vardi showed that expression complexity is typically one exponential higher than data complexity.

Example: First-order logic (relational calculus). Data complexity? LOGSPACE. Expression complexity? PSPACE. That’s not a small gap.

For fixed-point queries (related to my #SAT work), data complexity is PTIME, but expression complexity jumps to EXPTIME. The pattern holds across multiple query languages: the expression complexity hierarchy mirrors the data complexity hierarchy, shifted up by one exponential.

This matters because when database people say “this query language is complex,” you have to ask: complex for users who run the same query repeatedly on growing data? Or complex for users who run many different queries on fixed-size data? Different questions, different answers, same word.

It’s the same confusion I had with #SAT, just in a different domain. And it reinforces the point: “complexity” without context is meaningless.

And There Are More

I could keep going. Topological complexity (robot controller modes). Instance complexity (how hard is this specific input). Logical depth (computation time for near-shortest programs). State complexity (automata states for regular languages). Learning complexity (VC dimension vs Rademacher complexity).

Each isolates a different resource or structural property.

Why This Actually Matters

Back to my summer experiments. When measuring #SAT hardness, I was simultaneously measuring:

• Time complexity: solver runtime
• Circuit complexity: compiled decision diagram size
• Query/Sampling complexity: XOR constraints needed
• Proof complexity: Resolution width (implicitly)
• Parameterized complexity: formula treewidth

These all spike at the same place (phase transition) because they measure different facets of the same structure. The formula at critical density is hard in multiple senses. Not just slow, but structurally complicated.

That’s why the phase transition is interesting. It’s not “solvers are slow here.” It’s “the formula itself, in multiple formal senses, is complex here.”

And that’s the broader lesson. When someone says “this problem is complex,” the first question should be: complex in what sense? Time? Space? Communication? Proof length? Circuit size? Information content?

Each lens reveals something different. The real breakthroughs happen when you connect them. Communication lower bounds imply circuit lower bounds. Kolmogorov complexity connects to one-way functions. Query complexity connects to spectral graph theory (Huang’s sensitivity proof). Proof complexity connects to solver runtime.

The zoo isn’t a mess. It’s a toolkit. Yay.

Conclusion

As I’m applying to PhD programs, I’m looking for advisors who think about complexity from multiple angles. Who don’t just say “P vs NP” but understand hardness is structural, informational, communicational, logical, computational all at once.

If you’re navigating the complexity landscape (literally), I hope this taxonomy helps. Next time someone says “communication-complex” or “high proof complexity,” you’ll know what lens they’re using.

And maybe you’ll start seeing connections. That’s where it gets fun.

Note: If you want #SAT details, wait for the paper. If you think topological complexity doesn’t belong here (I know, I know), email me. If you’ve been nerd-sniped and want to dive deeper, the references in the documents I used are gold.

Thanks for reading. Have a nice day!

SeniorMars