Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In 1975, Baker, Gill, and Solovay presented a landmark paper on Relativizations of the P ?= NP question.

My question is fairly simple. Does their theory hold for all oracles? I ask this because I'm not well educated on the subject. Also, I recently stumbled across some material talking about nonrelativizing oracles because they are non-recursive. I'm guessing, though, that the 1975 result is valid for all oracles. I'm basically looking for a confirmation of this, so that I can stop researching p vs. np proofs with oracles.

share|cite|improve this question
Baker, Gill, and Solovay proved two facts, and both are in the form “There exists an oracle relative to which ….” Therefore, these results do not talk about all oracles. – Tsuyoshi Ito Nov 6 '11 at 18:47
@Tsuyoshi Ito: Does the possibility still exist, then, that using an oracle could still lead to a proof of P=NP? Sorry for my ignorance, by the way. I'm researching some analytic means, and I think that I'm getting close to a way to solve NP hard problems by analytic means. It seems to boil down to whether or not I can analyze a differnce equation (using sums, not a differential equation) in polynomial time. But I'm not sure I want to keep researching this since it essentially amounts to referencing an oracle. So I'd like to know what the theory says in this case. – Matt Groff Nov 6 '11 at 18:54
Because “using an oracle” is a very vague notion, any possibility exists. The result by Baker, Gill, and Solovay implies that whether P^A = NP^A or not depends on oracle A, and therefore if one argument applies to all oracles A, it cannot settle whether P=NP or not. – Tsuyoshi Ito Nov 6 '11 at 18:57
@Tsuyoshi Ito: Thanks very much for your help so far. My trouble is that I use a particular analytic method or algorithm. I essentially compute some nested sums, for all instances of k-SAT. The result that I get tells me how many satisfying truth assignments exist for the particular problem. So to me this is querrying an oracle or oracles $B$, so I'm worried that according to theory it will state that this oracle can be relativized. I hope this makes at least a little sense. I'm hoping that I can use this method without having to worry that $B$ can be relativized such that $P^B = NP^B$. – Matt Groff Nov 6 '11 at 19:44
What you are doing does not sound like anything related to whether P=NP or P≠NP, although I cannot follow much of your comment. – Tsuyoshi Ito Nov 6 '11 at 20:32
up vote 2 down vote accepted

A sum over instances of $k$-SAT is not an oracle computation, if the thing you are summing, such as $1$ if a solution and $0$ if not, is computable efficiently without an oracle.

An oracle is an auxiliary black box that computes (at constant time cost per query) a particular function $f(x)$ given $x$.

Given access to an extremely powerful oracle, such as a solver for the halting problem, $P$ and $NP$ can become equivalent, because computations that used to be hard in polynomial time now become trivial, by encoding them as halting problems and asking oracle for the answer. This is the easy half of the Baker Gill Solovay theorem, where an oracle to decide all problems in PSPACE is strong enough to obliterate the difference between P and NP, because P can simulate any NP computation in polynomial space and with polynomial overhead.

The more subtle part of B-G-S is to construct an oracle that advantages NP over P to the extent that it separates the two classes when they were not known to be different (and might be the same) for computation without an oracle. For this you need an oracle that provides little information if you ask it the wrong question, and a large amount of information if you guess exactly the right question to ask, so that an NP machine gains power in ways that a P machine does not.

share|cite|improve this answer
Thanks for your answer. I'm still a little shaky. Basically, I compute the number of satisfiable truth assignments for a given k-SAT conjunctive normal form of a function. I'm unsure, but guessing that that's the oracle. If I have a function that's satisfiable, I can produce a certificate by determining the truth assignments using this oracle. So I think that I'm computing $f(x)$ for a given k-SAT function $x$. But maybe that's where I'm mistaken. I I don't access particular instances of truth assignments, though, so maybe that's where I avoid computing $f(x)$. – Matt Groff Nov 6 '11 at 22:04
Let's say you are counting the number of solutions $x$ to $F(x)=0$ where $x$ is a string of $n$ bits. If the algorithm is to run through strings $x$ and count how many are solutions, this is not an oracle computation in the sense that testing whether a string is a solution is cheap enough that getting it for free (through an oracle) does not improve the complexity of the problem. If that's not what you are doing, note that counting satisfying assignments is in #P which is a harder class than NP. A certificate for the number of solutions could be of exponential length. – zyx Nov 6 '11 at 22:13

As Tsuyoshi stated the issues are not as clear cut as you may think. The relation between diagonalization and relativization is more complicated. BGS shows that there are oracles that relativized to them $\mathsf{P}$ is equal to $\mathsf{NP}$ (take any $\mathsf{PSpace\text{-}complete} problem), and there are oracles that relativized to them they are not equal (which is more complicated).

If you believe that they are not equal, then the easier results is what is useful. Since simple diagonalization arguments relativize (because they only use machines as black box, so the proof should work even if you replace them with their relativized version), you cannot separate them in the real world with a simple relativization (otherwise it would also separate them in relativized to a $\mathsf{PSpace\text{-}complete}$ oracle).

BGS result can be strengthened to: no simple diagonalization can separate $\mathsf{P}$ from $\mathsf{NP}$ (we have to define formally what it a diagonalization and when it is simple).

Informally you can think of simple diagonalization as black box separation, i.e. if the proof that there is a problem in $\mathsf{NP}$ which is not in $\mathsf{P}$ does not depend on the particular code of the machine solving that $\mathsf{NP}$ problem then the proof cannot work.

(I tried to simplify and make it easy to understand, so don't take it as completely correct. If you want to understand the details see Kozen's old paper, Fortnow's survey, and a more recent paper by Impagliazzo, Kabanets, and Kolokolova).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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