Relativization

In the grand quest of computer science, few questions loom as large as understanding the ultimate limits of computation. Problems like the famous P versus NP question challenge the very foundation of what we consider "easy" or "hard" to solve. Yet, despite decades of effort, these central questions remain unanswered, suggesting a fundamental obstacle in our standard methods of proof. This article introduces a powerful conceptual tool designed to probe the nature of this obstacle: relativization. By exploring the idea of an "oracle"—a hypothetical black box that can solve a specific problem instantly—we can create alternate computational universes to test the robustness of our theorems. In the following chapters, we will first delve into the "Principles and Mechanisms" of relativization, defining Oracle Turing Machines and discovering the profound "relativization barrier" they reveal. Subsequently, in "Applications and Interdisciplinary Connections," we will see how this concept acts as a crucial litmus test for proofs and provides deep insights into fields from cryptography to quantum computing, forever changing how we view the structure of computation itself.

Imagine you are a detective trying to solve a complex case. You have your methods: deduction, gathering evidence, interviewing witnesses. This is your "computational power." Now, imagine you are given a magic telephone. You can pick it up, ask any single "yes/no" question about the case ("Was the butler in the library at midnight?"), and instantly get a correct answer. This magic telephone is an ​​oracle​​. It doesn't solve the whole case for you, but it gives you a powerful new tool.

In complexity theory, we formalize this idea with an ​​Oracle Turing Machine​​. It's a standard computer, but with a special ability: it can query a "black box," the oracle, about a specific problem. We might write the problem the oracle solves as a language $L$. The machine can write any string $w$ and, in a single step, ask the oracle, "Is $w$ in $L$?" The oracle's answer is instantaneous and always correct. The set of problems our deterministic polynomial-time detective can solve with this magic phone is called $\text{P}^{L}$.

What's the first, most basic thing we can say about having an oracle? It can't hurt. A detective with a magic telephone can still do everything a detective without one can. He can simply choose not to use it. In the same way, any problem that is already in $\text{P}$ (solvable in polynomial time without an oracle) is also in $\text{P}^{L}$ for any oracle $L$ imaginable. The computer can just run its original program and ignore the oracle entirely. This gives us our first fundamental rule: $\text{P} \subseteq \text{P}^{L}$. The same logic applies to other classes, so $\text{NP} \subseteq \text{NP}^{L}$, and so on. The oracle is, at worst, a free upgrade.

But it can be much more than that. It can be a truly transformative tool. Consider the class $\text{NP}$, which includes problems like the famous Boolean Satisfiability Problem (SAT). An $\text{NP}$ machine has its own kind of magic: it can non-deterministically "guess" a potential solution and then check it. What happens if we give this guessing machine an oracle for SAT? We are giving a non-deterministic machine access to an oracle for an $\text{NP}$-complete problem. The result is a dramatic leap in power. The new class of problems this machine can solve, $\text{NP}^{\text{SAT}}$, is known as $\Sigma_{2}^{P}$, the second level of a vast structure called the polynomial hierarchy. The combination of two different kinds of "magic"—guessing and the oracle—has propelled us into a new, more complex computational realm.

This leads to a profound question: Does adding an oracle fundamentally rewrite all the laws of computation? Are there any universal truths that hold steady, no matter which magic telephone we're given?

Remarkably, the answer is yes. One of the cornerstone results in complexity theory is ​​Savitch's Theorem​​. In our world (without oracles), it tells us something astonishing: any problem that can be solved by a non-deterministic machine using a polynomial amount of space ($\text{NPSPACE}$) can also be solved by a deterministic machine using a polynomial amount of space ($\text{PSPACE}$). In short, $\text{NPSPACE} = \text{PSPACE}$. The ability to "guess" gives no advantage when it comes to memory usage.

The proof of Savitch's theorem is a beautiful, recursive algorithm. It checks if a machine can get from a starting configuration to an accepting one by asking: "Is there a halfway point on the path?" It then recursively asks the same question for the first and second halves of the journey. This process of breaking the problem down continues until it's just checking a single step.

Now, what happens if we give both the non-deterministic machine and the simulating deterministic machine access to the same oracle, say $A$? The deterministic machine can still execute the exact same recursive strategy. When it needs to check if one configuration can lead to another in a single step, and that step involves an oracle query, the deterministic simulator simply makes the same query to its own oracle. The oracle is just another rule of the game, and the recursive logic of the proof is completely indifferent to what the rules are. The proof ​​relativizes​​. Consequently, for any oracle $A$, it remains true that $\text{NPSPACE}^{A} = \text{PSPACE}^{A}$. We've found a law of computational physics that appears to be universal.

If a truth like Savitch's Theorem is universal, it's tempting to think that all fundamental relationships, like the one between $\text{P}$ and $\text{NP}$, must also be universal. Surely, either $\text{P}=\text{NP}$ or $\text{P} \neq \text{NP}$ is a fundamental law, and it should hold true no matter what oracle we introduce.

This is where the story takes a sharp and brilliant turn. In 1975, Theodore Baker, John Gill, and Robert Solovay proved a result that shook the foundations of complexity theory. They showed that, unlike Savitch's Theorem, the relationship between $\text{P}$ and $\text{NP}$ is not universal. It depends entirely on the oracle you choose. They constructed two different computational universes.

​​Universe A: The Great Collapse​​

First, they showed there exists an oracle $A$ such that $\text{P}^{A} = \text{NP}^{A}$. How is this possible? Imagine an oracle that is incredibly powerful—so powerful it can solve any problem in $\text{PSPACE}$. Let's call this oracle $A_{\text{PSPACE}}$. A machine in $\text{P}^{A_{\text{PSPACE}}}$ can now solve even famously hard $\text{NP}$ problems with ease. It just uses its polynomial-time brain to reformat the $\text{NP}$ problem into a single, clever question, which it then hands to the omniscient oracle. The oracle's immense power effectively "lifts" the deterministic $\text{P}$ machine up to a much higher level, allowing it to match the power of a non-deterministic $\text{NP}$ machine with the same oracle. The distinction between them is washed away by the tidal wave of the oracle's power.

​​Universe B: The Great Divide​​

Next, and this is the crucial part, they constructed another oracle, $B$, for which $\text{P}^{B} \neq \text{NP}^{B}$. The construction of this oracle is a delicate act of diagonalization. In essence, the oracle $B$ is specifically tailored to be unhelpful to any possible polynomial-time deterministic machine. It watches every $\text{P}$ machine try to solve a specific problem and then carefully plants an answer in the oracle that makes that machine fail. An $\text{NP}$ machine, however, can use its guessing ability to find that planted answer and succeed. This oracle is designed to create a gap between $\text{P}$ and $\text{NP}$, and it succeeds.

So we have two consistent, mathematically sound universes. In Universe A, $\text{P}$ and $\text{NP}$ are the same. In Universe B, they are different. What does this mean for us, here in the real, unrelativized world?

It means that any proof technique that works equally well in both universes is useless for settling the $\text{P}$ versus $\text{NP}$ question. Most of the standard tools in the complexity theorist's toolkit—simulation, diagonalization, the kinds of arguments used to prove Savitch's theorem—are of this type. They ​​relativize​​. If you used such a technique to prove, say, $\text{P} \neq \text{NP}$, your proof would also have to work if we gave all the machines in it the oracle $A$. But in that universe, we know $\text{P}^{A} = \text{NP}^{A}$. Your proof would be proving a falsehood, which means your proof must be wrong. This profound obstacle is known as the ​​relativization barrier​​. It tells us that a proof that settles $\text{P}$ versus $\text{NP}$ must be non-relativizing. It must use some deep, intrinsic property of computation that is true in our world but is broken by at least one of these artificial oracle worlds.

This is not just a story about $\text{P}$ versus $\text{NP}$. The relativization barrier is a lens through which we can examine the boundaries of our knowledge across all of computation.

For instance, consider the relationship between classical and quantum computers. Can quantum computers ($\text{BQP}$) solve problems that classical randomized computers ($\text{BPP}$) cannot? We have a result showing there is an oracle $O$ where $\text{BQP}^{O}$ is strictly larger than $\text{BPP}^{O}$. This is a major reason for optimism about quantum computing! But is it a definitive proof that $\text{BQP} \neq \text{BPP}$? No. Because of the relativization barrier, we know this result alone isn't enough. We must remain humble about the limits of what this single "snapshot" of a quantum-friendly universe can tell us about our own.

Perhaps most beautifully, the theory of relativization shows the incredible robustness of our computational framework. What if a physicist were to discover a real, physical process that could solve a problem known to be undecidable by any Turing machine—a true "magic box"? Would this shatter the Church-Turing Thesis and invalidate all of computer science? The answer is a resounding no. Theory is already prepared for this. We would simply say, "Ah, you have discovered a physical instantiation of an oracle for an undecidable language." We would then begin studying the complexity of problems relative to this new oracle. The framework doesn't break; it elegantly absorbs the new discovery, demonstrating that the concept of the oracle machine is one of the most powerful and flexible ideas in all of science. It provides a language for what we know, what we don't know, and even for that which we imagine might be unknowable. This is the quest that barriers like relativization—and others like the ​​natural proofs barrier​​—set out for us: to not only find the answers, but to understand the very nature of the questions themselves.

We have now learned the rules of a fascinating game—the game of oracle machines. We've seen how to equip our familiar Turing machines with a magical black box that can solve a particular problem in a single step. But this is more than just a technical curiosity. This is where the real adventure begins. By choosing different oracles, we can create entire new computational universes, each with its own laws of what is easy and what is hard.

In this chapter, we will become explorers of these alternate realities. Our goal is not merely to catalogue strange new worlds, but to use them as a laboratory. By observing what is true in all possible worlds, what is true in some, and what is true in only a select few (like our own!), we gain an unparalleled insight into the fundamental nature of computation, the limits of mathematical proof, and the deep connections between seemingly disparate fields of science.

Perhaps the most famous application of relativization is in illuminating why the greatest unsolved problem in computer science, $P$ versus $NP$, is so maddeningly difficult. The question asks whether every problem whose solution can be quickly verified ($NP$) can also be quickly solved ($P$). Decades of effort by the world's brightest minds have yielded no answer. Relativization gives us a profound reason why: any proof technique that is "generic" enough to work regardless of the presence of an oracle is doomed to fail.

This was the stunning conclusion of a seminal 1975 paper by Baker, Gill, and Solovay. They showed that one can construct two perfectly consistent computational universes that give opposite answers to the $P$ vs. $NP$ question. We can see this principle vividly with the analogous, smaller-scale question of whether Logarithmic Space equals Nondeterministic Logarithmic Space ($L$ vs. $NL$).

Imagine we build a universe with an oracle for TQBF, the language of all true quantified Boolean formulas. This oracle is incredibly powerful, as TQBF is complete for the class $PSPACE$. In a world with access to this oracle, it turns out that $L^A$ becomes equal to $NL^A$. The immense power of the oracle provides a "shortcut" that allows a deterministic machine to simulate a nondeterministic one without needing much extra space. Yet, we can just as easily construct a different universe with a carefully crafted "Pathfinder Oracle" $B$. This oracle is designed to encode a maze problem that is easy for a nondeterministic machine (which can guess the path) but hard for a deterministic one. In this second universe, $L^B$ is demonstrably not equal to $NL^B$.

The implication is staggering. Since we can build worlds where these classes are equal and worlds where they are not, no proof of $L=NL$ or $L \neq NL$ can be found if that proof's logic would also apply in these oracle worlds. This "relativization barrier" tells us that resolving these questions requires a proof that is "non-relativizing"—a proof that somehow exploits a special property of our universe, one that doesn't hold when an arbitrary oracle is attached.

The collapsing effect can be even more dramatic. With that same $PSPACE$-complete oracle, not only do $P$ and $NP$ become equal, but the entire Polynomial Hierarchy—an infinite tower of increasingly complex classes—collapses down to the first level, $P$. It's as if a computational skyscraper has been flattened into a bungalow.

This power to create contradictory worlds makes relativization a powerful litmus test for our proof techniques. If a theorem we prove about complexity classes holds true for any oracle, we say it "relativizes." This is a sign that the theorem captures a deep, structural truth about computation itself, one that is robust enough to survive in any conceivable computational reality.

A beautiful example of this is the relationship between different kinds of probabilistic algorithms. The class $ZPP$ (zero-error) consists of problems solvable by algorithms that are always correct but might sometimes fail to give an answer. The classes $RP$ and $coRP$ (one-sided error) allow for algorithms that might be wrong, but only in one direction. It is a fundamental fact that a problem is in $ZPP$ if and only if it is in both $RP$ and $coRP$. This elegant identity, $ZPP = RP \cap coRP$, is so fundamental that it holds true in every oracle world; that is, $ZPP^A = RP^A \cap coRP^A$ for any oracle $A$. Its proof is constructive and does not depend on any special properties of our world.

However, some of our most celebrated theorems fail this test. The landmark result $IP = PSPACE$ proved that problems solvable with an interactive proof (where a mighty Prover convinces a skeptical Verifier) are exactly the same problems solvable with a polynomial amount of memory. The proof was a work of genius, relying on a technique called "arithmetization" that transforms logical statements into polynomials. But what happens if we introduce an oracle? It turns out there are oracles for which $IP^A \neq PSPACE^A$. This tells us something profound: the $IP=PSPACE$ proof is not a generic truth of computation. It relies on the specific algebraic structure of our world, a structure that an arbitrary, unstructured oracle can disrupt. Relativization isolates and highlights the ingenuity of such non-relativizing proofs.

Relativization also warns us when our intuition is flawed. For example, a simple "padding" argument shows that if $P=NP$, then the exponential-time analogues $E$ and $NE$ must also be equal. This seems like a straightforward, logical extension. But relativization reveals a crack in this intuition. It is possible to construct a bizarre oracle world where $P^A = NP^A$, but simultaneously $E^A \neq NE^A$! This shocking result shows that the simple padding argument does not relativize, and the connection between polynomial and exponential time is more subtle than it first appears. It teaches us that intuitions honed in our specific computational reality may be mere local customs, not universal laws.

The insights gained from this "computational cosmology" are not confined to complexity theory. They have deep and practical implications for cryptography, quantum computing, and even the philosophy of information.

​​Cryptography​​: In cryptography, we often want to build complex tools, like a secure digital signature, from simpler building blocks, like a one-way function (a function easy to compute but hard to reverse). A "black-box" construction is one that uses the building block as an oracle, without peeking at its internal code. Relativization provides a powerful method to prove that certain constructions are impossible. For instance, it is known that one cannot build a collision-resistant hash function (a function for which it's hard to find two inputs that produce the same output) in a black-box way from a one-way permutation. The reason? We can construct an oracle world where one-way permutations exist, but collision-resistant hash functions do not. Since any black-box proof must work in all oracle worlds, this separation proves its impossibility. This saves cryptographers from chasing down blind alleys and guides them toward constructions that require non-black-box techniques.

​​Quantum Computing​​: When quantum computing was in its infancy, relativization provided some of the first strong theoretical evidence for its potential power. Simon's algorithm is a quantum algorithm that can solve a specific, contrived problem exponentially faster than any possible classical algorithm. The problem is defined by an oracle. This result creates a relativized world where the class of problems efficiently solvable by a quantum computer, $BQP^O$, is demonstrably larger than the class of problems efficiently solvable by a classical probabilistic computer, $BPP^O$. While this doesn't prove that $BQP \neq BPP$ in our world, it showed that the quantum model of computation was not just a re-skinning of the classical one; it had access to a genuinely new kind of computational structure, one that could provide immense speedups, at least in some worlds.

​​Algorithmic Information Theory​​: Perhaps most philosophically, relativization challenges our very notion of complexity and information. The Kolmogorov complexity of a string, $K(x)$, is the length of the shortest computer program to produce it—a measure of its inherent randomness. Chaitin's constant, $\Omega$, is a number whose binary digits are maximally random; the string of its first $n$ bits, $\Omega_n$, has complexity roughly $n$. It is the very definition of incompressible information. But what if we give our computer an oracle for the Halting Problem, a mythical device that knows whether any given program will ever stop? Relative to this oracle, the complexity of $\Omega_n$ plummets from $n$ to a mere $\log(n)$. The oracle acts like a perfect dictionary, turning what was once random gibberish into a simple, short description. This demonstrates that complexity is not an absolute property of an object, but a relationship between that object and the computational power of the observer.

By building and studying these strange new worlds, we return to our own with a deeper appreciation for its unique structure. Relativization is the tool that lets us see the features of our computational reality not as given, but as one remarkable possibility among an infinity of others.