14
$\begingroup$

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?

$\endgroup$
7
  • 5
    $\begingroup$ Even when oracles make perfect sense (as in the case of P and NP) the complexity classes are highly sensitive to the representation of the oracle. Indeed, the restrictions on the complexity classes also restrict how oracle information can be accessed and this leads to some complex interactions. For example, Baker, Gill, Solovay do warn that their results do not hold for all seemingly reasonable representations of oracles. $\endgroup$ Sep 20, 2011 at 11:23
  • 6
    $\begingroup$ A more rigorous way to define these classes is to think of the definition of P^A as a primary thing and P as the shorthand for P^∅, and similarly to NP. The same idea applies to many classes, but not to every class possibly imaginable. $\endgroup$ Sep 20, 2011 at 12:01
  • $\begingroup$ @ Tsuyoshi -- yes, but what is logic of the formulas by which complexity classes are defined? $\endgroup$ Sep 20, 2011 at 18:30
  • $\begingroup$ @ Francois -- I didn't know about that. Is there an example of a seemingly nice representation of oracles for which the Baker-Gill-Solovay results are known to fail? $\endgroup$ Sep 21, 2011 at 5:23
  • 2
    $\begingroup$ Noah, here is one that is "barely reasonable" but illustrates the point. Represent the elements of the set A in order using tick marks (1s) separated by blanks (0s). (So {3, 5,...} would be 1110111110...) Even if the set A is highly informative, it takes a lot of computing power to extract significant information using this representation. $\endgroup$ Sep 21, 2011 at 17:44

3 Answers 3

15
$\begingroup$

[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.

$\endgroup$
3
  • $\begingroup$ Also Impagliazzo, Kabanets, and Kolokolova's paper "An Axiomatic Approach to Algebrization" from STOC 2009: cs.sfu.ca/~kabanets/Research/algebrization.html $\endgroup$
    – Kaveh
    Sep 21, 2011 at 19:10
  • $\begingroup$ @Timothy Forgive my ignorance, but I didn't quite get what is the flaw in the argument you provided for $P \not= NP$. $\endgroup$
    – stillanoob
    Mar 11, 2018 at 15:34
  • $\begingroup$ @ibrahim5253 : $P=NP$ does not imply that $P^A = NP^A$ for all $A$. If you study carefully the definitions of $P^A$ and $NP^A$, you will see that there is no reason to expect that $P^A = NP^A$ even if $P=NP$, any more than one should expect that $(x+y)^2 = x^2 + y^2$ for real numbers $x$ and $y$. It's only if we blindly manipulate formulas that the temptation for the false inference arises. $\endgroup$ Mar 18, 2018 at 17:42
5
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ This states "the definition must be in terms of machines". But it does not state what properties of the machine shall be allowable in the definition, or what type of formula shall be used to quantify over the machines. Intuitively, this whole issue is clear enough. The question is, what does it mean precisely. $\endgroup$ Sep 20, 2011 at 1:36
  • 3
    $\begingroup$ The proper way to making it precise is to follow Tsuyoshi Ito’s comment above. There is no way around the fact that there may be more than one way of relativizing a given class. $\endgroup$ Sep 20, 2011 at 14:50
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.