5
$\begingroup$

Oracles do not exist. If one did exist, then you would replace them with a subroutine with computational requirements and you would no longer need an "Oracle". Thus, Oracles do not exist almost by definition. I don't understand how one can make an mathematical argument based on something that does not exist (excluding unbounded memory machines, of course). Have a problem, ask the "magic" Oracle, problem solved $O(1)$ time. Of course you can't say anything about what is happening in the oracle, because its "magic". From this point of view, Turing Machines (bizarre fetish formalism if you ask me) with Oracles do not exist. Also, that X historic proofs rely on oracles makes oracle arguments valid is a circular argument.

$\endgroup$
9
  • 7
    $\begingroup$ In a "real" sense, nondeterministic TMs don't exist either. That's not to say that they're not worthy of study. $\endgroup$ Dec 9, 2014 at 20:36
  • $\begingroup$ @RickDecker Well ... we can mimic what a non-deterministic automaton is supposed to do by different means that are computationally equivalent. But we cannot do that with oracles. $\endgroup$
    – babou
    Dec 9, 2014 at 21:58
  • $\begingroup$ @babou : $\:$ However, we can do that for "sufficiently efficient" oracles too. $\;\;\;\;$ $\endgroup$
    – user12859
    Dec 9, 2014 at 22:10
  • 3
    $\begingroup$ @babou That depends what the oracle is for. You can perfectly well simulate an oracle for 3-SAT. $\endgroup$ Dec 9, 2014 at 22:38
  • 1
    $\begingroup$ I do not understand the recurrent questionning of infinite memory machines. That is only a convenient way, based on a well regulated use of the concept of limit, to analyze uniformly a whole family of machine differing only by memory size. All are real (as much as the word has meaning), and all computation use only finite memory, hence doable by a finite memory machine. The "infinite memory machine" is just a set of similar finite ones. Complexity analysis is the theoretical complement telling us which finite machines are necessary. $\endgroup$
    – babou
    Dec 9, 2014 at 23:06

6 Answers 6

12
$\begingroup$

Oracles are a very general formalization of the idea, "If I could solve $X$ efficiently, I could use that to solve $Y$ efficiently." I accept that it sounds a bit silly to go as far as "If I could solve problem $X$ in constant time, I could use that to solve $Y$ efficiently" but, actually, that doesn't make any real difference at the level of detail we're working at, here.

For example, consider an oracle $O_1$ that can solve SAT in constant time, versus an oracle $O_2$ that solves SAT in, say, cubic time. The problems you can solve in polynomial time with access to $O_1$ are exactly the same as the ones you can solve in polynomial time with access to $O_2$. Sure, the polynomial will be better if you use $O_1$, but it's still a polynomial if you use $O_2$. In fact, the answer won't change whatever polynomial bound you assume on the running time of the oracle so we choose to simplify the analysis by choosing the simplest polynomial possible: $1$.

In some cases, you can see oracle arguments as hedging your bets. Although you lead your question with "Oracles don't exist", we don't actually know that. Suppose somebody produced a polynomial-time algorithm for SAT tomorrow. Wouldn't it be a shame if all we could solve with it was SAT? But because we have all kinds of oracle reductions available to us, we could already solve any NP-complete problem efficiently (the many-one reductions used to prove problems NP-complete are just a very restricted kind of oracle reduction). Conversely, if somebody proves tomorrow that SAT has no efficient algorithm, then all that work on oracles tells us that all the other NP-complete problems are also genuinely hard.

But remember that oracle arguments are conditional: if I could do $X$, then I could also do $Y$. If it turns out that you can't do $X$ then, OK, maybe you can't do $Y$ after all. But it's still a perfectly valid what-if question. So, for example, it still makes sense to consider Turing machines with an oracle for the halting problem, even though we know for a provable fact that no Turing machine can actually solve the halting problem. There's nothing wrong with asking the what-if, as long as we remember that it is a what-if.

To address a couple of other points,

I don't understand how one can make an mathematical argument based on something that does not exist (excluding unbounded memory machines, of course).

So we're allowed to use some non-existent things but not others? Why?

Turing Machines (bizarre fetish formalism if you ask me)

Are you trying to get a rise out of me, Agent Kujan?

Also, that X historic proofs rely on oracles makes oracle arguments valid is a circular argument.

Yes, that's circular. But it's also a strawman: I've never heard anyone make that argument.

$\endgroup$
10
$\begingroup$

There are several applications to oracles.

First, there is usage in proving lower bounds (i.e. Turing reductions): if you know that a problem $L$ cannot be solved within some complexity (or computability) class $C$, and you show that an oracle to $L'$ allows you to solve $L$ within $C$, then you can conclude that $L'$ is also not in $C$.

Second, there is a pure-mathematical interest in adding oracles. For example, consider an oracle to $A_{TM}$. The fact that even under this oracle there are problems that are undecidable leads to the beautiful concept of the arithmetical hierarchy. Moreover, there is an interesting connection to logic - the arithmetical hierarchy corresponds to definable sets.

$\endgroup$
5
$\begingroup$

There are many mathematical objects that "do not exist" (afaik, and whatever that means), and which have been the support of mathematical reasonning for centuries (maybe not many centuries). The first example that comes to mind is the real numbers, and more generally non denumerable sets. All you need is that the non-existing object have properties that are defined well enough so that you can reason with them.

Using an axiomatic system requires in no way the existence of a physical model that could serve as a model for these axioms. The funny thing is that physicists themselves do that all the time. They imagine laws that could govern the universe to see whether they may explain better observed phenomena. Many (most) of these systems turn out not to fit reality, though understanding why is often a source of knowledge and progress.

You can see Turing Machines as an axiomatic system that describe a kind of computation that seems to fit well what is physically realizable (as stated by the Church-Turing thesis). Lambda Calculus is another one, different but equivalent. But nothing forbid adding more axioms that leads to new theories of computability that are mathematically sound ... but probably useless for effective computation in this world (I do not know about other worlds).

But they are not more useless than the non-computable reals that are implicitly (hopefully) taught in all schools of the world. I just mean that the distinction with computable reals is not usually made.

Oracles are just like extra axioms, or extra computational object like the non computable reals, that are helpful for abstract reasonning, but not so helpful for actual computation.

Now, existence is also a somewhat relative matter. In your question you state at first

Oracles do not exist. If one did exist, then you would replace them with a subroutine with computational requirements and you would no longer need an "Oracle".

I answered so far about oracle that are not realizable at all, since that seemed to be what you were concerned with in your question. But being realizable, i.e. computable, has degrees and that is what complexity analysis is about. Not being computable is just the worst case. Replacing the oracle by a subroutine imposes to you the complexity of that subroutine. But maybe you want to hypothesize that there are faster ways.

Some problems are not computables (what I talked about), then some others are computable but with high complexity. It may be that versions with lower complexity do not exist, as far as we know, but we can wonder what would happen if they did. Indeed, progress in physics has introduced the possibility of new computing technology (quantum computing) that may change the complexity of some problems. This is enough to justify oracle based analysis, even for problem that already have a solution, as the oracle allows us to analyse what would happen with a more efficient solution.

And then there are problem for which we do not know what the complexity is, and analyzing complexity of the use of solutions of such problems can be done only with oracles.

$\endgroup$
1
$\begingroup$

It is incorrect to say that oracles do not exist by mathematical definition. An oracle is merely an abstraction for something that solves a problem. When making logical arguments, you have to start with assumptions (and you should state them as formally as possible.) Proving that "If I could do X, then I could do Y" can be useful for a number of reasons. One of those reasons can be as simple as that it's entirely possible to do X, there are multiple ways to do it, and which one is chosen by a given implementation is simply irrelevant to what you're proving. Another is that it may be possible to do X and that your proof that that would lead to the ability to also do Y would have significant consequences if someone else comes along and shows a way to do X.

In cryptography, for instance, it's common for papers to make arguments based on oracles that allow an attacker to determine the ciphertext for a given plaintext. Clearly, there are plenty of ways to accomplish that. How the attacker does so is not relevant to the argument being made, though, thus it is abstracted away as a 'black box.'

$\endgroup$
0
$\begingroup$

"one can make an mathematical argument based on something that does not exist (excluding unbounded memory machines, of course)" by making sure it works for ("unbounded memory machines" and) something that does exist - random number generators.

Just say "if for each bit produced by that RNG, the bit was a 1 if and only if the contents of the oracle tape at that time encoded an element of the set, then the combination will have a high-enough probability of halting with the right answer without exceeding its resource limitations."

$\endgroup$
-3
$\begingroup$

I found nice answers to my concerns/confusions (OP) in these threads:

Why is Relativization a barrier?

The reason this transfer from oracle-less framework to framework with oracles works is that simple diagonalization is based on black-box simulation of TMs and it doesn't matter how machines works, whether it has an oracle or not.

Why are non-relativizing proofs preferred to relativizing ones?

This leaves one question which you haven't asked: Why do we care about relativized results? I don't know the historical reason. It might be that these techniques are commonplace in related ares that served as sources of inspiration. At the very beginning, people might have expected that relativized results do imply absolute results.... Since that point, much less attention has been given to oracle results, and they are now quite unfashionable. They have become an object of study in their own right, but with no pretensions to be relevant for separating P from NP.

This paper backs up the previous quote: Relativization: a Revisionistic Retrospective, Hartmanis, et. all.

http://www.csee.umbc.edu/~chang/papers/revisionist/rev-book.pdf

$\endgroup$
2
  • 4
    $\begingroup$ This is not an answer. If you need to clarify your question, please edit it rather than posting an answer. Answers on SE should actually answer the question. $\endgroup$
    – reirab
    Dec 9, 2014 at 22:55
  • $\begingroup$ agreed the cited questions do not answer the original question very directly although there may be some relevant material cited. you say you found answers to "my concerns/ confusions"; did you write this question under another name? $\endgroup$
    – vzn
    Dec 12, 2014 at 6:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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