27
$\begingroup$

This may be a basic question, but I've been reading and trying to understand papers on such subjects as Nash equilibrium computation and linear degeneracy testing and have been unsure of how real numbers are specified as input. E.g., when it's stated that LDT has certain polynomial lower bounds, how are the real numbers specified when they are treated as input?

Improve this question
$\endgroup$
2

6 Answers 6

Reset to default
33
$\begingroup$

I disagree with your accepted answer by Kaveh. For linear programming and Nash equilibria, floating point may be acceptable. But floating point numbers and computational geometry mix very badly: the roundoff error invalidates the combinatorial assumptions of the algorithms, frequently causing them to crash. More specifically, a lot of computational geometry algorithms depend on primitive tests that check whether a given value is positive, negative, or zero. If that value is very close to zero and floating point roundoff causes it to have the wrong sign, bad things can happen.

Instead, inputs are often assumed to have integer coordinates, and intermediate results are often represented exactly, either as rational numbers with sufficiently high precision to avoid overflow or as algebraic numbers. Floating point approximations to these numbers may be used to speed up the computations, but only in situations where the numbers can be guaranteed to be far enough away from zero that the sign tests will give the right answers.

In most theoretical algorithms papers in computational geometry, this issue is sidestepped by assuming that the inputs are exact real numbers and that the primitives are exact tests of the signs of roots of low-degree polynomials in the input values. But if you are implementing geometric algorithms then this all becomes very important.

Improve this answer
$\endgroup$
12
  • $\begingroup$ I had liked the part of Kaveh's answer where he suggested that there are alternate models of computation, as this seemed to be in line with what I had read in the paper I was looking at. That said, I didn't really know the answer...I've un-accepted Kaveh's answer for now. I had actually suspected that algebraic numbers might have something to do with it. Anyway, thank you for taking the time to weigh in on my question...I will think and read further before I accept an answer. $\endgroup$
    – user1338
    Oct 9, 2010 at 18:08
  • $\begingroup$ I haven't said that it is a good model for CG, my point was that even when authors say the inputs are real numbers, they are not really real numbers. I agree with you that I shouldn't have included CG among the others. I have read a very small number of CG papers, is BSS model that well-established in theoretical CG papers? $\endgroup$
    – Kaveh
    Oct 9, 2010 at 18:43
  • 1
    $\begingroup$ Pardon my ignorance, but what does BSS stand for? $\endgroup$
    – user1338
    Oct 9, 2010 at 18:48
  • 1
    $\begingroup$ The BSS model is a theoretical model that assumes that arbitrary real numbers are available. What's done in CG involves actual implementations of a model that is generally restricted to algebraic numbers. Also the CG implementations are far from unit cost per operation. So they're not the same thing. See e.g. the LEDA real number model, citeseerx.ist.psu.edu/viewdoc/… $\endgroup$
    – David Eppstein
    Oct 9, 2010 at 21:02
  • 10
    $\begingroup$ @Kaveh: No. Geometric algorithms are designed to be correct, in the real RAM model, for arbitrary real input, not just for rational input. In particular, there are geometric algorithms that cannot be implemented exactly, because they use primitives that are trivial on the real RAM but for which no efficient algorithm is known for the (realistic) integer RAM. The best example is the sum of square roots problem: Given two sets $S$ and $T$ of positive integers, is $\sum_{s\in S} \sqrt{s} > \sum_{t\in T}\sqrt{t}$? $\endgroup$
    – Jeffε
    Oct 10, 2010 at 7:28
15
$\begingroup$

You might also have a look at Andrej Bauer's talk on The Role of the Interval Domain in Modern Exact Real Arithmetic, which surveys some of the different approaches to specifying computation over the real numbers both in theory and practice.

Improve this answer
$\endgroup$
8
$\begingroup$

This is not a direct answer to your question, more of a response to Raphael. There has been quite some work recently specifying real number computations using coinduction. Here are some articles on the topic.

They hardly cover the full spectrum of real number computation, but progress is being made to chip away at various problems.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Nice idea but since you can only have countably many coinductive definitions, this approach can not cover whole $\mathbb{R}$. Do I overlook something? Or did I misunderstand and the aim is to represent at least some more numbers exactly? $\endgroup$
    – Raphael
    Oct 10, 2010 at 15:50
  • $\begingroup$ Good point. I'm not sure what the limitations of the coinductive approach is. The approach is in its infancy. $\endgroup$
    – Dave Clarke
    Oct 10, 2010 at 18:18
7
$\begingroup$

Edited/Corrected based on the comments

When authors talk about real number inputs in linear programming, Nash equilibrium computation, ... in most papers (papers which are not on the topic of computation/complexity over real numbers) they don't really mean real numbers. They are rational numbers and numbers that arise from them due to their manipulations (algebraic numbers). So you can think of them as represented by finite strings.

On the other hand, if the paper is on computability and complexity in analysis, then they are not using the usual model of computation, and there are various incompatible models of computation/complexity over real numbers.

If the paper does not specify a model of computation over real numbers, you can safely assume that it is the first case, i.e. they are just rational numbers.

Computational Geometry is different. In most papers in CG, if the authors does not specify what is the model which with respect to it the correctness and complexity of an algorithm is being discussed, it can be assumed to be the BSS (a.k.a. real-RAM) model.

The model is not realistic and therefore the implementation is not straight-forward. (This is one of the reasons that some people in CCA prefer Ko-Friedman/TTE/Domain theoretic models, but the problem with these models is that they are not as fast as floating-point computation in practice.) The correctness and complexity of the algorithm in the BSS model does not necessarily transfer to the correctness of the implemented algorithm.

Weihrauch's book contains a comparison between different models (Section 9.8). It is only three pages and worths reading.

(There is also a third way, which may be more suitable for CG, you may want to take a look at this paper:

Chee Yap, "Theory of Real Computation according to EGC"

where EGC is Exact Geometric Computation.)

Improve this answer
$\endgroup$
6
  • $\begingroup$ I think the paper I'm primarily interested in specifies a model, given that it includes the sentence, "We now formally define our model of computation." The paper is called "Lower Bounds for Satisfiability Problems," and there seems to be some discussion of linear decision trees and query polynomials. So, I think that is the answer I was looking for there...thanks. I'll re-read the paper and see if I can make sense of it. $\endgroup$
    – user1338
    Oct 9, 2010 at 17:29
  • 2
    $\begingroup$ I disagree. This is the wrong model for computational geometry. See my more detailed answer below. $\endgroup$
    – David Eppstein
    Oct 9, 2010 at 17:49
  • 1
    $\begingroup$ @Kaveh: I think you should say that they are rational numbers, not floating-point numbers. Exact rational numbers are easy to represent by finite strings, and in many applications (e.g., those related to linear programming) intermediate results will also be rational numbers if your inputs are rational numbers. (Of course, as David Eppstein pointed out, comp. geom. is a notable exception in the sense that intermediate results are usually not rational.) $\endgroup$
    – Jukka Suomela
    Oct 9, 2010 at 18:26
  • $\begingroup$ @Jukka: You are right, I will replace floating-point with rational. $\endgroup$
    – Kaveh
    Oct 9, 2010 at 18:31
  • 5
    $\begingroup$ Nope. When I write "real number", I really mean "real number", and by that I mean really real number, really from the reals. Really. In particular, in the paper @Philip talks about, I have to assume the algorithms works for arbitrary real input, so that I can apply results from non-standard analysis. $\endgroup$
    – Jeffε
    Oct 10, 2010 at 7:23
6
$\begingroup$

The computational complexity of computations over real numbers is considered by Blum, Cucker, Shub, and Smale. Here's a partial description of the book:

The classical theory of computation has its origins in the work of Goedel, Turing, Church, and Kleene and has been an extraordinarily successful framework for theoretical computer science. The thesis of this book, however, is that it provides an inadequate foundation for modern scientific computation where most of the algorithms are real number algorithms. The goal of this book is to develop a formal theory of computation which integrates major themes of the classical theory and which is more directly applicable to problems in mathematics, numerical analysis, and scientific computing. Along the way, the authors consider such fundamental problems as: Is the Mandelbrot set decidable? For simple quadratic maps, is the Julia set a halting set? What is the real complexity of Newton's method? Is there an algorithm for deciding the knapsack problem in a ploynomial number of steps? Is the Hilbert Nullstellensatz intractable? Is the problem of locating a real zero of a degree four polynomial intractable? Is linear programming tractable over the reals?

You may find a review of this book on ACM SIGACT News.

Improve this answer
$\endgroup$
6
  • $\begingroup$ This book looks very interesting, thank you. $\endgroup$
    – user1338
    Oct 9, 2010 at 17:15
  • $\begingroup$ You're most welcome. $\endgroup$
    – Sadeq Dousti
    Oct 9, 2010 at 19:07
  • 5
    $\begingroup$ It's worth noting that the BSS model of computation over the reals is controversial, for reasons much like what David Eppstein referred to in a comment above. For example: the BSS axiom that computing whether x < y takes one time step, for arbitrary reals x and y. By contrast, approaches like Type Two Effectivity (TTE) define machines that take as input approximations to reals, and output computable approximations to functions over the reals. The more time elapses, the better the input and output approximations can become. That approach feels more realistic to me. $\endgroup$
    – Aaron Sterling
    Oct 10, 2010 at 0:59
  • $\begingroup$ @Aaron Sterling: do you know of a good reference for Type Two Effectivity? $\endgroup$
    – Joshua Grochow
    Oct 11, 2010 at 14:12
  • 3
    $\begingroup$ @Joshua Grochow: Sorry I didn't get to this sooner. The book Kaveh linked to is the "Nielsen and Chuang" of TTE. However, it is so notation-laden that it would seem arcane to a casual reader. I would suggest, instead, the following tutorial slides of Vasco Brattka: cca-net.de/vasco/cca/tutorial.pdf $\endgroup$
    – Aaron Sterling
    Oct 12, 2010 at 17:42
3
$\begingroup$

They are not and they can not, in general. We can only treat a countable number of inputs (and outputs and functions) with our models of computation. In particular, any input has to be finite but not all real numbers have finite representations.

You could, I guess, assume some kind of oracle that yield the next digit of a certain real number upon request (sth like a stream). Otherwise you will have to live with (arbitrarily precise) approximations.

Improve this answer
$\endgroup$
2
  • $\begingroup$ If this is true then how can LDT deal with real numbers? I read something about "r-Linear Decision Trees" but didn't really understand what they were talking about in the paper, "Lower Bounds for linear satsifiability problems." $\endgroup$
    – user1338
    Oct 9, 2010 at 17:13
  • $\begingroup$ I bet they either cannot or they do not use Turing machines (or equivalent conecpts). The other answers that are not as strict/general as mine should shed some light on this. $\endgroup$
    – Raphael
    Oct 10, 2010 at 15:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.