How to judge the definition of computational complexity of reals is natural or suitable?

Question

As we know, definition of computational complexity of algorithm is almost without controversy, but the definition of computational complexity of reals or the computation models over reals is not in such a case. We know Blum and Smales' model and model in the book Computable Analysis. And seemingly, model in Computable Analysis is consistent with the classic model, but the definition of computational complexity of reals can not transplanted into classic model.

How to judge the definition of computational complexity of reals is natural or suitable?

And how to transplant the definition of computational complexity of reals into classic model?

Answer 1

I am not exactly sure what the question is here, but I can try to say a bit to clean up possible misunderstandings.

First of all, if we are talking about complexity of a map $f : \mathbb{R} \to \mathbb{R}$, it makes no sense to ask "What is a good representation for $\sqrt{2}$?" Instead, you have to ask "What is a good representation for all inputs of $f$?". Compare the situation with an easier one in discrete math: when you discuss an algorithm which takes a graph as an input, you do not ask "Should we represent the Petersen graph as as an adjancency list or as a binary matrix?" but instead you automatically think of a uniform representation which will work for all graphs.

Another word of warning. By changing the representation of the input data we can always make any problem (including a non-computable one) trivially computable: in order to make $f : A \to B$ computable, represent the elements of $A$ as pairs $(a, f(a))$. Then you can "compute" $f$ by the second projection. This shows that we need clear criteria of what it means to represent data.

I have written on several occasions about what it takes to represent the elements of $\mathbb{R}$. The answer depends on what structure of $\mathbb{R}$ you are trying to capture. If you are trying to capture no structure, then you can represent all reals with the empty list, for example. A reasonable list of conditions for a representation of $\mathbb{R}$ is that it needs to be such that:

1. The arithmetical operations $+$, $\times$, $-$, $/$ are computable, as well as the absolute value $|{-}|$.
2. There is a program which takes (the representation of) a real $x$ and $k \in \mathbb{N}$ and outputs integers $p, q$ such that $|x - p/q| \leq 2^{-k}$, i.e., it is possible to compute arbitrarily good rational approximations.
3. There is a program which takes (representations of) reals $x$ and $y$ and terminates if, and only if, $x < y$, i.e, the strict order is semidecidable.
4. Given a sequence (of representations of) $(x_n)_n$ such that $|x_{n+1} - x_n| \leq 2^{-n}$ a representation for the limit $\lim_n x_n$ can be computed.

There are old theorems (see introduction to this paper for references) which explain why these conditions are the correct one. These theorems also show that any two such representations of reals are computably isomorphic, that is, we can translate between them with programs. This sets up some criteria for correctness that throw out faulty ideas.

For example, I hear people say things like "rational numbers can be represented by finite information, so let's use that for rational numbers, and the irrational numbers will have to be represented by infinite information". This sort of thing does not work because it breaks the fourth condition above (consider a limit of irrational numbers -- how will you tell that it is converging to a rational?).

Another example which the above conditions eliminate is the Blum-Shub-Smale model because in it you cannot compute limits of sequences. It is better to say that the BSS model works on a discrete ordered subfield of reals (generated by whatever parameters are present), not on the reals themselves.

Among the correct representations of reals some are more efficient than others, although this is a somewhat difficult topic to discuss because real numbers are infinite objects. Matthias Schröder pointed out that for a reasonable theory of complexity one has to pay attention to the topological properties of the representation.

Finally, how should we measure the complexity of a map $f : \mathbb{R} \to \mathbb{R}$, assuming we have a good representation of $\mathbb{R}$? Because $x \in \mathbb{R}$ is represented by a function, or an infinite stream of information, or some such, we should be using one of the higher-type notions of complexity. Which one probably depends on the representation you are using.

The BSS model is a also a reasonable circuit complexity model in which we count arithmetical operations. It's just good to keep in mind that this model is not about real numbers, but about something else.

Answer 2

Another model possibly to explore, is that of the Feasible RAM model. This is a modified real RAM model for Real computation, Feasible RAM, or a modified RAM model which uses both the discrete, and real valued arithmetic operations. This model allows for real, and discrete operations, and the Turing model, is interchangeable with it. The Feasible RAM model has precision defined with uncertainty, which means that $<_{k}$ allows comparisons of real numbers only up to a variable uncertainty 1/(k+1). This allows for approximative computations. Also, as Vasco Brattkaa and Peter Hertlingb state in Feasible Real Random Access Machines - the models of Turing, and that of Feasible Real RAMs, are related. All functions computable on a Turing machine in time $O(t)$ are computable on a RAM in time $O(t)$, and in the obverse case there some overhead for the Turing machine that computes the function(if real RAM computes the function in $O(t)$ the TM computes the function in $O(t^{2}log(t)log(log(t)))$. As pointed out topological considerations are useful, one doesn't know if there is any topological context developed for this model of computation that allows for real computations -which has uncertainty in precision.