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

  • 1
    $\begingroup$ In the second line, you probably mean P^B != NP^B (the A must be a typo) $\endgroup$ Aug 27 '10 at 21:58
  • $\begingroup$ 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). $\endgroup$ Aug 27 '10 at 22:48
  • $\begingroup$ I'm not sure on what basis you "suppose" that the two consequences follow? $\endgroup$ Aug 27 '10 at 22:54
  • $\begingroup$ 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. $\endgroup$ Aug 27 '10 at 22:57
  • $\begingroup$ @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}$. $\endgroup$ Aug 28 '10 at 1:14

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

  • 1
    $\begingroup$ 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. $\endgroup$ Aug 28 '10 at 1:18
  • $\begingroup$ 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. $\endgroup$
    – Kurt
    Aug 28 '10 at 17:53
  • $\begingroup$ 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. $\endgroup$ Aug 28 '10 at 20:28

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.


Your Answer

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

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