Definition of relativization of complexity class - MathOverflow

Definition of relativization of complexity class

2011-09-19T22:20:25Z

Is there any general definition, for a class $C$ of languages, what is the relativized class $C^A$ for an oracle $A$?

Usually, these classes and their relativizations seem to be defined in an ad-hoc way. For example, $P$ is the class of languages decided by poly Turing machines, $P^A$ is the class of languages decided by poly Turing machines with access to $A$. There is not any logic, as far as I can see, to tell you how to add $A$ to the definition of $P$.

Obviously, the definition of a relativization of $C$ depends on more than simply the set of languages that comprise $C$. For example, $P = NP$ is unknown, but there exists an oracle $A$ such that $P^A \neq NP^A$. So, the definition of the relativization should somehow have access to the "defining property" of $C$. But, is there any rigorous way to do this?

Answer by Joseph O'Rourke for Definition of relativization of complexity class

2011-09-20T00:13:42Z

Perhaps this could be of some help?: Lecture notes of a Weizmann course by Oded Goldreich (.ps here). On the first page, he (or his note-taker) says

Given any two complexity classes $C_1$ and $C_2$, where $C_2$ is the class of oracles, it is not always possible to have a natural notion of what is the class $C_1^{C_2}$—it is not necessarily the case that for every complexity class $C_1$ we can define its relativization to $C_2$.

Then he outlines "some conditions under which such a relativization can be done" via oracle machines. Although this material is a decade old by now, I believe relativization continues to be generally defined in terms of oracle Turing machines: those with a distinguished oracle tape that is consulted whenever the machine enters an "oracle state."

Added. Thus if $C$ is a complexity class of languages accepted by Turing machines satisfying some type of (time/space) resource bound, then $C^A$ is the class of languages accepted within the same resource bounds by machines that can make "oracle calls" to $A$ at unit cost. For example, DTIME$^A(t(n))$ is the class of all languages decidable in $O(t(n))$ steps given access to the oracle $A$.

Answer by Kaveh for Definition of relativization of complexity class

2011-09-20T17:19:13Z

There isn't one correct definition of a relativization of a complexity class. Depending on the circumstances there are different definitions which are useful. So we don't have a single way of defining the relativization even for a fixed complexity class.

As an example, consider the complexity class $\mathsf{L}$. Using one definition we can show that there is an oracle $A$ s.t. $\mathsf{L}^A=\mathsf{PSpace}^A$. On the other hand, hierarchy theorem relativizes, so $\mathsf{L}^A \neq \mathsf{PSpace}^A$ for all $A$. These results look contradictory at the first sight but they are not. The key point is that they are using different definitions. Both definitions are used in the literature.

Depending on what we want to achieve we have different suitable relativizations. This is similar (though more subtle) to reductions, there are several of them, some results hold w.r.t. one kind of reductions and fail w.r.t. another one.

Answer by Timothy Chow for Definition of relativization of complexity class

2011-09-21T02:30:44Z

[EDIT: I wrote my original answer when I was in a bit of a hurry. I have now expanded my answer.]

The short answer is no. The simplest way to see that $C^A$ cannot possibly depend only on $C$ and $A$ as sets of strings is the following spurious argument that has confused generations of students. Assume that $P=NP$. Then for all oracles $A$, $P^A = NP^A$. But by Baker–Gill–Solovay, we know that there exists an oracle $A$ such that $P^A \ne NP^A$. This is a contradiction. Hence $P\ne NP$. Q.E.D., and I await my $1 million check.

The standard notation $C^A$ is an abuse of notation. A class per se cannot be relativized; one must specify a model of computation and provide that model of computation with access to an oracle. Choosing different models of computation, or different oracle access mechanisms, may give you different relativizations. For example, space-bounded classes are notoriously tricky to relativize, as explained in this paper by Hartmanis et al. The trouble is that it's not obvious what the "right" oracle access mechanism is in certain cases.

Having said that, I think it is a fascinating open-ended problem to try to "formalize" the concept of relativization in a way that would allow one to rigorously prove statements of the form, "such-and-such a type of argument relativizes and therefore cannot (for example) separate $P$ from $NP$." Though this is a very tempting idea, there is still no fully satisfactory theory along these lines. Probably the best attempt in this direction so far is the unpublished manuscript Relativizing versus nonrelativizing techniques: the role of local checkability, by Arora, Impagliazzo, and Vazirani, but this is really just a first attempt. For example, in his paper The role of relativization in complexity theory, Fortnow argues that there are certain important limitations to the Arora–Impagliazzo–Vazirani model. Fortnow's paper is recommended reading if you want to work on this open problem yourself.