<p>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?</p>

<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2011-09-24T09:16:03.587Z
Your question rambles a bit: are you asking if there are notion of limited power oracles ?
Suresh Venkat
CC BY-SA 3.0
2011-09-24T16:17:33.020Z
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.
Jesse Stern
CC BY-SA 3.0
2011-09-24T20:09:29.447Z
I see. is there an "imagined result statement" that you are envisaging - maybe that would help clarify things.
Suresh Venkat
CC BY-SA 3.0
2011-09-26T01:02:10.030Z
If you have a better way I of stating the question I would welcome an edit (as I see you have already done once)
Jesse Stern
CC BY-SA 3.0
2011-10-01T15:05:15.213Z
I'm not entirely clear on what you're asking, but I believe this paper is relevant (and may even answer your question): http://cseweb.ucsd.edu/~russell/ias.ps
Joshua Grochow
<cc.complexity-theory><complexity-classes><relativization>
Abilities of Restricted Relativization in Proving Conjectures
Jesse Stern
# Abilities of Restricted Relativization in Proving Conjectures

(Asked by: username_0 on 2011-09-24)

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?

**Tags:** cc.complexity-theory, complexity-classes, relativization
> **Comments:**
> **username_1**: Your question rambles a bit: are you asking if there are notion of limited power oracles ?  
> **username_0**: 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.  
> **username_1**: I see. is there an "imagined result statement" that you are envisaging - maybe that would help clarify things.  
> **username_0**: If you have a better way I of stating the question I would welcome an edit (as I see you have already done once)  
> **username_2**: I'm not entirely clear on what you're asking, but I believe this paper is relevant (and may even answer your question): http://cseweb.ucsd.edu/~russell/ias.ps  

---

## 0 answers

