A unified framework for comparing plain, prefix, monotone, and decision complexities. Oracles and relativization.
We've now seen three major complexity notions: plain C(x), prefix K(x), and monotone KM(x). Each has its strengths. This chapter steps back to see the big picture: what do all these complexities have in common, and how do they differ?
The general scheme: each complexity is defined by a class of "machines" (decompressors) and a notion of "description." Different constraints on the machines give different complexities, but the same universality argument works in each case.
Decision complexity CD(x) uses a different kind of "description": instead of a program that produces x, we use a program that decides membership in a set containing x.
This is a fundamentally different perspective. Plain complexity asks: "what is the shortest program that outputs x?" Decision complexity asks: "what is the smallest decidable set that singles out x (within a size constraint)?"
The relation: C(x) ≤ CD(x) + O(1). Decision complexity is never less than plain complexity (up to a constant). Intuitively, if you can decide membership in a small set containing x, you can also enumerate that set and find x by its index, giving a short description.
How do the different complexities relate? Here is the hierarchy:
In words: plain ≤ decision ≤ prefix, and all three are within O(log n) of each other for strings of length n. The differences are logarithmic, not linear.
| Pair | Relationship | Gap |
|---|---|---|
| C vs K | C(x) ≤ K(x) ≤ C(x) + 2 log C(x) + O(1) | O(log n) |
| C vs KM | KM(x) ≤ K(x) + O(1) | O(1) |
| K vs KM | KM(x) ≤ K(x) ≤ KM(x) + O(log n) | O(log n) |
| C vs CD | C(x) ≤ CD(x) + O(1) | Can be O(log n) |
For most applications (incompressibility method, combinatorial proofs), the O(log n) difference is negligible and any complexity works. The distinction matters only for precise characterizations of randomness (which require K or KM).
Each complexity has a conditional version: C(x|y), K(x|y), KM(x|y), CD(x|y). The conditional version measures how much information x contains beyond what y provides.
The general pattern: conditional complexity C(x|y) is defined using a decompressor that takes both a description and the "hint" y as input. The universal machine for conditional complexity simulates all conditional decompressors.
Conditional complexities satisfy the same basic properties: non-growth under computable transformations, counting arguments, upper semicomputability (or lower semicomputability for the associated semimeasures).
An oracle is a set A ⊆ N that a machine can query: "is n ∈ A?" in one step. Machines with oracle access can compute things that ordinary machines cannot.
The complexity with oracle A is denoted CA(x), KA(x), etc. It measures the shortest description when the decompressor has access to oracle A.
A particularly important case: A = the halting set (the set of all programs that halt). With a halting oracle, complexity becomes computable! CHalt(x) can be computed, because we can now check all programs up to a given length and determine which ones halt.
The oracle hierarchy: A0 = ∅ (no oracle), A1 = halting set, A2 = halting set for machines with oracle A1, etc. Each level gives strictly more computational power. Complexity relative to An is denoted C(n)(x).
The different complexities form a natural hierarchy, unified by the general scheme. Here is the complete picture:
Each level adds a constraint that makes the complexity more structured but potentially larger. The extra structure buys us better theorems (Kraft inequality, chain rule with O(1) error, Levin-Schnorr characterization).
The visualization below shows how the different complexity notions relate for a given string length n.
For strings of length n, the different complexities are close but not identical. The bars show typical values and their relationships.
| Complexity | Machine type | Key property |
|---|---|---|
| C(x) | Arbitrary partial computable | Simplest. Counting argument. |
| CD(x) | Total decidable sets | Uses set membership, not output. |
| K(x) | Prefix-free domain | Kraft inequality. Probability link. |
| KM(x) | Monotone mapping | Monotone in prefix order. Dimension. |
| CA(x) | Oracle access to A | Relativized complexity. |