<p>Whether or not $P^{A,B}$ equals $NP^{A,B}$ is going on the particular oracle languages A and B that you are using.  Iirc, in the BGS paper the language A is TQBF (or any other PSPACE-complete language).  The language B, somewhat ironically, is actually defined via a diagonalization construction.  Now, if you use the construction from the paper and apply it to TMs with an A oracle, then the resulting language B will be such that $P^{A,B} \ne NP^{A,B}$.  On the other hand, if you stick with the original language B from the paper, it will depend on the details of B's construction.  If B is in PSPACE (I don't know offhand if it is or not), then a TM with an A oracle could simulate any queries to B, and you should have $P^{A,B} = NP^{A,B}$.</p>

<p>The bottom line, though, is that this has nothing to do with consistency--it is just a technical question about the specific oracle languages A and B (and you could get different answers depending on the particular choices of A and B that you use).</p>

CC BY-SA 2.5
2010-08-28T01:18:24.623Z
Kurt: You are correctly pointing out the difference between oracles as sets, and oracles constructions, which is, I believe, the main source of Monoid's confusion.  Given that it is the source of Monoid's confusion, you might want to clarify your notation a bit along the following lines.  Let $A(X)$ be an oracle construction (that is, construct $A$ relative to $X$).  When you say "If you use the construction from the paper on TMs with an $A$ oracle" you can write that as $B(A)$, and contrast it with $B(\emptyset)$.  This is what you are already doing, just with less ambiguous notation.
Joshua Grochow
CC BY-SA 2.5
2010-08-28T17:53:21.710Z
Joshua, thanks.  At this point I think I'll let my answer stand unedited, but I'll try to use the preferred terminology (also from you comment to Ross up above) in the future.  BTW, how would you pronounce A⊕B?  I want to say "A disjoint union B", but it sounds unnecessarily verbose.
Kurt
CC BY-SA 2.5
2010-08-28T20:28:00.050Z
Fair enough.  It's pronounced "A join B".  Technically, A join B is usually defined as $A \oplus B = \{0x : x \in A \} \cup \{ 1y : y \in B \}$k.  If you are considering polytime degrees rather than sets, then A join B is defined in the usual order-theoretic way (hence the term "join"), as the least upper bound of A and B under the preorder defined by polytime reductions.  From that perspective, the 0x union 1y definition I gave above is just a particular construction of a set having the right polytime degree.
Joshua Grochow
CC BY-SA 2.5
2010-08-27T23:47:49.253Z
2010-08-27T23:47:49.253Z
Kurt
<p>You write "the theory with only oracle A", what this means?
The oracle A is a set, the theory can prove some property on A, 
or construct a set with certain properties. 
The inconsistency of a theory with only oracle A, in any reasonable interpretation,
will imply the inconsistency of the theory. </p>

<p>It is worth noticing that the provability of such oracles A,B do tell something.
As proven in Hartmanis and Hopcroft paper "Independence results in computer science",
such A,B imply that there exist an oracle C, such that neither $P^C=NP^C$ and $P^C \neq NP^C$ are provable in any sound with a RE set of axioms theory, which means that the question is undecidable. C is not constructed as the join of A,B but mimic one of them from some point.</p>

CC BY-SA 2.5
2010-08-28T10:24:13.197Z
2010-08-28T10:24:13.197Z
Sebastian Ben Daniel
<p>My question may be stupid, but let's take the Baker-Gill-Soloway theorem as an example :</p>

<p>There exists an oracle A such as $P^A = NP^A$ and an oracle B such as $P^B \neq NP^B$.</p>

<p>If we take both oracles A and B, I suppose we have $P^{A,B} = NP^{A,B}$ and $P^{A,B} \neq NP^{A,B}$, and then, theory wouldn't be consistent.</p>

<p>What says us that the theory with only oracle A is consistent ? If such theory isn't consistent, then there could be non-relativizing proofs of $P \neq NP$.</p>

CC BY-SA 2.5
2010-08-27T21:58:01.850Z
In the second line, you probably mean P^B != NP^B (the A must be a typo)
Suresh Venkat
CC BY-SA 2.5
2010-08-27T22:48:36.680Z
If I'm not mistaken $P^{A,B} = NP^{A,B}$ in this case, namely there exists an algorithm (given the oracles A and B) such that P = NP (just use A and not B).
Ross Snider
CC BY-SA 2.5
2010-08-27T22:54:24.283Z
I'm not sure on what basis you "suppose" that the two consequences follow?
András Salamon
CC BY-SA 2.5
2010-08-27T22:57:53.627Z
I have to agree with Andras in that I don't see why the consequences should follow. Surely this depends on the relationship between A and B. So the specific oracles matter.
Joe Fitzsimons
CC BY-SA 2.5
2010-08-28T01:14:46.797Z
@Ross: Relative to $A,B$ (which is usually written $A \oplus B$), if you just use $A$ then you get that $NP^{A} \subseteq P^{A} \subseteq P^{A \oplus B}$.  However, there could be a language in $NP^{B} \subseteq NP^{A \oplus B}$ that is not in $P^{A}$.
Joshua Grochow
<cc.complexity-theory>
Shouldn't relativisation contain consistency proof ?
Ludovic Patey
# Shouldn't relativisation contain consistency proof ?

(Asked by: username_0 on 2010-08-27)

My question may be stupid, but let's take the Baker-Gill-Soloway theorem as an example :

There exists an oracle A such as $P^A = NP^A$ and an oracle B such as $P^B \neq NP^B$.

If we take both oracles A and B, I suppose we have $P^{A,B} = NP^{A,B}$ and $P^{A,B} \neq NP^{A,B}$, and then, theory wouldn't be consistent.

What says us that the theory with only oracle A is consistent ? If such theory isn't consistent, then there could be non-relativizing proofs of $P \neq NP$.

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: In the second line, you probably mean P^B != NP^B (the A must be a typo)  
> **username_2**: If I'm not mistaken $P^{A,B} = NP^{A,B}$ in this case, namely there exists an algorithm (given the oracles A and B) such that P = NP (just use A and not B).  
> **username_3**: I'm not sure on what basis you "suppose" that the two consequences follow?  
> **username_4**: I have to agree with Andras in that I don't see why the consequences should follow. Surely this depends on the relationship between A and B. So the specific oracles matter.  
> **username_5**: @Ross: Relative to $A,B$ (which is usually written $A \oplus B$), if you just use $A$ then you get that $NP^{A} \subseteq P^{A} \subseteq P^{A \oplus B}$.  However, there could be a language in $NP^{B} \subseteq NP^{A \oplus B}$ that is not in $P^{A}$.  

---

## 2 answers

### Answer by username_6 on 2010-08-27. Score: 5 | Accepted answer

Whether or not $P^{A,B}$ equals $NP^{A,B}$ is going on the particular oracle languages A and B that you are using. Iirc, in the BGS paper the language A is TQBF (or any other PSPACE-complete language). The language B, somewhat ironically, is actually defined via a diagonalization construction. Now, if you use the construction from the paper and apply it to TMs with an A oracle, then the resulting language B will be such that $P^{A,B} \ne NP^{A,B}$. On the other hand, if you stick with the original language B from the paper, it will depend on the details of B's construction. If B is in PSPACE (I don't know offhand if it is or not), then a TM with an A oracle could simulate any queries to B, and you should have $P^{A,B} = NP^{A,B}$.

The bottom line, though, is that this has nothing to do with consistency--it is just a technical question about the specific oracle languages A and B (and you could get different answers depending on the particular choices of A and B that you use).

> **Comments:**
> **username_5**: username_6: You are correctly pointing out the difference between oracles as sets, and oracles constructions, which is, I believe, the main source of Monoid's confusion.  Given that it is the source of Monoid's confusion, you might want to clarify your notation a bit along the following lines.  Let $A(X)$ be an oracle construction (that is, construct $A$ relative to $X$).  When you say "If you use the construction from the paper on TMs with an $A$ oracle" you can write that as $B(A)$, and contrast it with $B(\emptyset)$.  This is what you are already doing, just with less ambiguous notation.  
> **username_6**: Joshua, thanks.  At this point I think I'll let my answer stand unedited, but I'll try to use the preferred terminology (also from you comment to Ross up above) in the future.  BTW, how would you pronounce A⊕B?  I want to say "A disjoint union B", but it sounds unnecessarily verbose.  
> **username_5**: Fair enough.  It's pronounced "A join B".  Technically, A join B is usually defined as $A \oplus B = \{0x : x \in A \} \cup \{ 1y : y \in B \}$k.  If you are considering polytime degrees rather than sets, then A join B is defined in the usual order-theoretic way (hence the term "join"), as the least upper bound of A and B under the preorder defined by polytime reductions.  From that perspective, the 0x union 1y definition I gave above is just a particular construction of a set having the right polytime degree.  

---

### Answer by username_7 on 2010-08-28. Score: 2

You write "the theory with only oracle A", what this means?
The oracle A is a set, the theory can prove some property on A,
or construct a set with certain properties.
The inconsistency of a theory with only oracle A, in any reasonable interpretation,
will imply the inconsistency of the theory.

It is worth noticing that the provability of such oracles A,B do tell something.
As proven in Hartmanis and Hopcroft paper "Independence results in computer science",
such A,B imply that there exist an oracle C, such that neither $P^C=NP^C$ and $P^C \neq NP^C$ are provable in any sound with a RE set of axioms theory, which means that the question is undecidable. C is not constructed as the join of A,B but mimic one of them from some point.


---

