11
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ For your first question, "natural" is a very subjective notion and depending on the person you ask, one or the other definition will be considered as the most natural. As for "suitable", it depends: the BSS model seems suitable for computational geometry or computational algebraic geometry, and the model in Computable Analysis is more suitable for... computable analysis! I do not understand the second question. $\endgroup$ – Bruno Nov 19 '14 at 8:02
  • $\begingroup$ @Bruno, thank you for your comment, I think the model in Computable Analysis, and do not know how to apply the definition of computational complexity to computation of real number over classic model like Turing Machine, since the computational complexity of real number over model in Computable Analysis depends on the representation of it,namely, the input for computation of it. $\endgroup$ – XL _At_Here_There Nov 19 '14 at 8:08
  • 3
    $\begingroup$ You seem to think there is a complexity notion for real number computation which is independent of the representation of reals. What makes you think so? This is not the case in classical complexity either. It matters whether you have a tape or a RAM machine, it matters whether you represent graphs by adjancency lists or 01-matrices, etc. $\endgroup$ – Andrej Bauer Nov 19 '14 at 14:59
  • 3
    $\begingroup$ But it's not true that the complexity does not depend on the representation. By switching to a stupid representation you can always ruin the complexity of an algorithm. The question to ask is: "What is a good representation of the input?" For discrete problems this is much easier to answer than for real numbers, because one has a good feel for what it means to "don't waste bits". $\endgroup$ – Andrej Bauer Nov 20 '14 at 12:35
  • 3
    $\begingroup$ the BSS model seems suitable for computational geometry — See my answer to a related question. The Real RAM model used by computational geometers predates Blum, Shub, and Smale by almost a decade. $\endgroup$ – Jeffε Nov 23 '14 at 15:07
13
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Thank you very much for your answer, and so many references. I feel uncomfortable about some notions of computational complexity, let me read the reference and think about for a time, and give an example, if I can find suitable one to explain why I am so uncomfortable( this sounds funny, But my experience tell me if I feel uncomfortable, there must be something singular) $\endgroup$ – XL _At_Here_There Nov 21 '14 at 0:47
  • 4
    $\begingroup$ In my experience, feeling uncomfortable about new knowledge is a good sign, and usually it is a prerequisite for enlightenment. $\endgroup$ – András Salamon Nov 21 '14 at 14:19
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you give some reference for the feasible RAM model? $\endgroup$ – XL _At_Here_There Nov 23 '14 at 11:09
  • $\begingroup$ See above in the area, "... this reference states ..." has a link to the article. $\endgroup$ – user3483902 Nov 23 '14 at 14:05
  • 2
    $\begingroup$ Thanks for pointing out to the Brattka & Hertling work, I was going to mention it by then I forgot. I would just like to point out that the Feasible RAM model does not include any higher-order functions, in particular it cannot compute the limit of a (rapid) Cauchy sequence, so I would not count it as implementing "the reals" precisely. It can compute one limit "on the top level", so to speak (see the part of the paper where they speak about rational approximations of functions). $\endgroup$ – Andrej Bauer Nov 26 '14 at 7:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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