# Are all computational complexity results oracle results?

When talking about the complexity of a given operation, say multiplication of numbers, one usually counts the number of "elementary operations" that are required.

For example, a common argument says that multiplying two $n$-digit numbers with the schoolbook standard method takes $O(n^2)$ operations, while more sophisticated techniques give complexities closer to $O(n)$.

In these examples, what is counted is the number of single-digit operations, but then the complexity of those operations themselves is not taken into account. Isn't this then essentially an oracular result, in the sense that it tells us the number of operations we have to perform, provided we have a magical box solving single-digit operations?

The issue you are highlighting is that of computation model, which is how we measure the resource consumption of an algorithm. The computation model specifies how to assign time complexity, space complexity, and so on to a given program (whose syntax it also specifies). There are three popular computation models:

• Turing machines, of various sorts.
• Boolean circuits.
• RAM machines, of various variants.

A variant of the RAM machine can be specified in terms of the allowable basic operations, which is the issue that you encountered. For Boolean circuits, the analog is the set of allowable gates, and for Turing machines there seems to be no such analog.

In contrast, here is an actual example of how oracles are used in theoretical computer science.

A submodular function is a set function $f\colon 2^U \to \mathbb{R}$ (i.e., a function that accepts a subset of $U$ as input, and returns a real output) that satisfies a technical constraint known as submodularity.

Submodular optimization is the field which studies how to optimize submodular functions relative to various constraints (including no constraints).

A typical problem is:

Given a submodular function, find its minimum.

How is the submodular function "given" to us? It could be given to us as a truth table (i.e., the value of $f(A)$ for any $A \subseteq U$), but this is not a realtistic assumption. Rather, there is often an efficient algorithm that computes $f$. In most cases we are interested in an algorithm which is oblivious to the exact algorithm used to compute $f$. In these cases, we are looking for an algorithm which has oracle access to $f$, that is, the function $f$ is provided as an input oracle.

(In other cases we would like to use the code for $f$. This happens usually when $f$ has a particular structure, for example if it is a coverage function. In cryptography we sometimes want to "open the black box" even when $f$ has no particular structure.)

No, this has nothing to do with oracles. We don't use a "magic box" for that; we use a small circuit. Usually our computers work with binary, so "single-digit" means "single-bit". And hopefully you can see how single-bit operations can be implemented with gates: for instance, multiplication of two single bits is just an AND gate, and so on. So there is no need for an oracle; we just implement those single-bit operations directly.

Oracles are something different.

• sure, but what I mean is: those operations themselves still have a time cost, which I guess sort of becomes the "unit of measurement" with which all other time costs are counted. Isn't this essentially what oracles are? Black boxes whose inner working we do not track when counting the total cost of an algorithm? – glS Jul 21 '18 at 18:04
• @glS, I understand why you might get that impression, but no, that's not what oracles are. Oracles are something different. If you're asking what is the unit of measure, the unit of measure for computational complexity depends on the model of computation, but it might be the number of gates in a circuit, or it might be the number of steps of a Turing machine, or the number of steps of an algorithm in a RAM model, etc. Informally, we often count the number of simple operations, without worrying too much about those formal models (but we can always refer to them if needed). – D.W. Jul 21 '18 at 19:35