0
$\begingroup$

/!\ I am not speaking about int or float, my question is about model of computation used to design and describe algorithms.

The integer numbers case

Many algorithms use integers and their complexities are almost always given using both the RAM model and the big $O$ notation.

Using the RAM model allows us to add 2 integers in constant time. Assuming that the machine word size is constant, we can't assume that the codings of those integers have to be shorter than a machine word due to the big $O$ notation. Indeed this would implie that those integers are constants and this is not acceptable. For instance, EXPTIME algorithms with integers inputs would become constant time algorithms.

In the other hand, we can't assume that the machine words are still bigger than the input, once again some EXPTIME algorithms would become constant time algorithms. For instance, adding two integers whose codings are exponential in the input size.

However, we can assume that machine word size is $O(\log n)$ where $n$ is the input size, in this way we avoid previous absurdities, we can't forget more than a $O(\log n)$ factor in the complexity. Thus, we have a good complexity theory for algorithms using only integers.

The real numbers case

In computational geometry or in data mining, we frequently meet real coordinate spaces, but some reals are not even computable. Consequently, the $O(1)$ hypothesis for basic operators would be really monstrous, some undecidable problems would become $O(1)$. In the other hand, floating point model prohibit accuracy or is too complicated to be used if we consider accuracy.

So, what could be a good model of computation for real numbers ?

My first (and only) idea is to assume that the entropy of a real number is bounded by an input size function.

$\endgroup$
4
  • 3
  • $\begingroup$ @D.W. Thanks ! I will look at cstheory before asking, next time. I would be not surprised if this BBS model was proved inconsistent. Do you think it's a good idea to assume that the entropy is bounded ? $\endgroup$
    – François
    Jun 23 '15 at 21:52
  • $\begingroup$ Yes, there are plenty. Did you search before asking? $\endgroup$ Jun 23 '15 at 21:56
  • $\begingroup$ @DavidRicherby Indeed, when I began to write it wasn't the same question, but I solved the first one writting and this one has spawned at the same time. Thus the first question has been transformed in this one whithout break. It's why I only searched here and not in the all world wide web. $\endgroup$
    – François
    Jun 23 '15 at 22:04