Relativization Strikes Again: Understanding Ph Vs Pp Through Oracle Separations

The Power of Relativization in Complexity Theory

Relativization is a powerful technique in computational complexity theory that allows comparing the relative computational power of complexity classes. It involves considering complexity classes in the context of oracle Turing machines. An oracle is an abstract device that can solve a decision problem in one step.

By relativizing complexity classes to different oracles, we can often obtain separations between classes that are otherwise hard or impossible to separate in the unrelativized setting. Although they do not imply unconditional separations, relativized separations provide deep insights into the structure and relationships between complexity classes.

Oracle Turing Machines and Relativized Complexity Classes

An oracle Turing machine is a modification of a regular Turing machine that has access to an oracle that can solve a decision problem in one step. We represent the oracle by a special oracle query state and tape. When the Turing machine enters the oracle query state, the oracle determines if the contents of the oracle tape represent a yes-instance or no-instance of the decision problem it solves.

Table of Contents

We can then define relativized complexity classes based on oracle Turing machines, such as PSPACEA to represent the class PSPACE relative to an oracle A. These classes consist of all languages decidable by machines from the unrelativized class but with access to the oracle A.

By choosing different oracles A and B, we can often obtain separations between PSPACEA and PSPACEB by diagonalization. This shows the machines with access to A can solve problems that those with B cannot. Although they do not entail unconditional separations, these oracle separations offer deep structural insights.

Separating Complexity Classes with Oracles

A key application of relativization is demonstrating separations between complexity classes using oracles. The high-level approach is:

Define languages LA in PSPACEA and LB in PSPACEB
Show LA is not in PSPACEB using diagonalization
Conclude that PSPACEA is not equal to PSPACEB

Therefore, there exist problems solvable in polynomial space given access to oracle A but not oracle B. This proves PSPACEA properly contains problems absent in PSPACEB. Although not an unconditional separation, this reveals insights into the relative power of oracles.

Some landmark relativized separations include oracle A such that P^A != NP^A, proving P != NP is not resolved by a simple diagonalization argument. Additionally, oracles for PH ^A != P^A show PH has greater computational power than P, even relative to oracles.

Case Study: Separating PH and PP with Oracles

As an illustrative case study, we can separate the polynomial hierarchy PH from probabilistic polynomial time PP using a random oracle. PH and PP both contain P and are contained in PSPACE.

First, we define the languages:

LA in PH relative to a random oracle R
LB in PP relative to a random oracle R

We can design LA such that relativized PH machines can query the random oracle R to solve LA. However, we can show using a counting argument that the probabilistic machines defining LB cannot reliably solve LA, since R is random and unpredictable.

Therefore, machines with LA as an oracle can compute LB, but the converse is not true. By diagonalization, this gives us PH^R != PP^R. So PH^R properly contains problems such as LA that are intractable for PP^R. Therefore, relative to the random oracle R, PH has greater computational power.

The Limitations of Relativization

Despite their utility for structural complexity insights, there are notable limitations to relativized separations:

They do not imply unconditional separations
Techniques like interactive proofs overcome relativization barriers
Random oracles may not accurately model complexity in the real world

Additionally, oracles are abstract external devices, whereas we often care more about the intrinsic complexity of a computational model itself. Therefore, we must beware of overinterpreting relativized separation results.

Looking Beyond Relativization: Algebraic and Interactive Proofs

Many researchers have looked beyond relativization to advance unconditional separation results in computational complexity. Two fruitful approaches are:

Algebraic techniques exploiting group theory and matrices
Interactive and probabilistically checkable proofs

Notable achievements include separating IP from PH using interaction and PCPs, and separating AM from PH using algebraic properties. These demonstrate sophisticated mathematical machinery can prove unrelativized separations between classes that otherwise resist relativization.

Therefore, while a valuable technique for building intuition, relativization does not tell the whole story about computational complexity. Mathematical and interactive proof techniques continue advancing our structural complexity understanding in the unrelativized setting where it truly counts.