principleModerate
How is it valid to use oracles in mathematical arguments?
Viewed 0 times
argumentsoraclesvalidhowusemathematical
Problem
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#34080, answer score: 12
Revisions (0)
No revisions yet.