Though everyone seems to say that P vs NP cannot be solved using relativization because there are oracles both $A$ and $B$ such that $\text{P}^A = \text{NP}^A$ and $\text{P}^B \neq \text{NP}^B$, why is it that oracles cannot quantified in terms of power much like how time and space are very strictly limited in reductions?

An example would be that one cannot say that a problem is in L because there is a reduction from the given problem to an L-Complete. They would clearly have to be more specific and be using a reduction that is log space or less as the problem would not necessarily be in L if it was polynomial time reducible to an L-Complete problem.

I guess my question ends up being, is there any way to quantify the power of given oracles in a manner such that they can be used for proving results that would not otherwise be provable using relativization?

  • 5
    $\begingroup$ Your question rambles a bit: are you asking if there are notion of limited power oracles ? $\endgroup$ – Suresh Venkat Sep 24 '11 at 9:16
  • $\begingroup$ Well it is obvious that there is a notion of limiting the power of oracles as one could simply restrict oracles to those that could not solve problems in a certain complexity class therefore bounding their power. My question is more along the lines of is there a way to bound oracles such that relativization can be used to prove more conjectures then if one was attempting to relativize with no restrictions on the power of oracles that can be used. $\endgroup$ – Jesse Stern Sep 24 '11 at 16:17
  • $\begingroup$ I see. is there an "imagined result statement" that you are envisaging - maybe that would help clarify things. $\endgroup$ – Suresh Venkat Sep 24 '11 at 20:09
  • $\begingroup$ If you have a better way I of stating the question I would welcome an edit (as I see you have already done once) $\endgroup$ – Jesse Stern Sep 26 '11 at 1:02
  • $\begingroup$ I'm not entirely clear on what you're asking, but I believe this paper is relevant (and may even answer your question): cseweb.ucsd.edu/~russell/ias.ps $\endgroup$ – Joshua Grochow Oct 1 '11 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.