Computing with reals...

Dealing with real numbers (as opposed to arbitrary fixed precision rationals) has always been an annoying problem facing the theory of computation. Many problems that we tend to address in theory are combinatorial in nature, and so it has been possible to either ignore the issue of how one deals with reals (ed: hmm...'deals with reals'...I like the sound of that), or pay a token obeisance via notions like strong NP-completeness.

Why is dealing with real numbers tricky ? Well, the first problem is one of representation: clearly we can't write down a real number. The second one is one of computation; assuming we have some black box that can store a real number, how can we add two such numbers ? multiply them ? do anything more complicated ? And how do we assign a cost to these operations ?

These are very complex questions, and there are far too many angles to cover in a single entry (or even in a single survey). But to emphasize that this is not merely a toy intellectual question, let me present some examples.

• TSP in the plane is not known to be in NP. The problem here is that the computation of a distance involves calculating square roots, and this introduces precision issues with the number of bits needed to represent an answer.
• A similar situation arises for Minimum Weight Triangulation, one of the original vexing problems in CG.
• A careless use of operators can collapse complexity classes rather easily. As Jeff points out in this post, the floor function can be exploited to collapse PSPACE to P !

It is therefore rather important to understand the complexity of operations on reals and be very careful about the definitions one uses in this regard. In practice what one often does is assume a set of operations and assign unit cost to each (the so-called unit-cost RAM model). Of course, the floor example above shows that we have to be somewhat careful in doing so.

The work by Ben-Or, and later by Steele and Yao, on algebraic decision trees is based on performing single algebraic operations with unit cost, and then proving lower bounds on the complexity of algorithms in terms of the number of "sign tests" needed. One can think of this as a generalization of a simple comparison test, and it is fairly effective at proving lower bounds in settings where standard models don't work too well.

In fact, one can generalize algebraic sign tests to polynomial satisfiability tests; given a collection of polynomials over a set of variables, the decision is an appropriate sign signature (this poly must be positive, that one must be negative, etc). These are the so-called semi-algebraic sets, and going back to Tarski's work on the first order decision theory of the reals, (it is decidable to check if a given sign signature can be achieved), much work has been done on understanding the structure of these sets. It is worth noting that the Collins decomposition, a kind of 'vertical decomposition' for semi-algebraic sets, is one of the tools exploited by Mulmuley in his proof separating P from NC without bit operations (Mishra has a nice survey on computational algebraic geometry).


The idea for this post started when Chandra Chekuri pointed me to a survey by Lenore Blum in the Notices of the AMS titled 'Computing over the Reals: Where Turing Meets Newton'. What spurred me further was a discussion I had at dinner the other night; a graduate student was asking the following question:

Is the Mandelbrot set undecidable ?

The discussion continued onto a longer argument over the algorithms from numerical analysis and how they compare to algorithms in the traditional 'Turing' sense that operate over 0-1 inputs.

The Blum survey is a fascinating overview of the landscape of real computations (Blum, Shub and Smale have a book on complexity and real computation as well). Critically, it develops tools for talking about the complexity of algorithms on reals, by developing ideas of computation over a ring with "black-box" rational, algebraic operators as atomic computing units.

Thus, an answer to the above question becomes immediate:

The Mandelbrot set is undecidable.

She also talks about the P vs NP question over complex numbers and the reals, (the "classical" P vs NP question is really over Z2), and establishes a connection between Hilbert's Nullstellensatz and satisfiability via the choice of ring. A quote from the article:

I have endeavored to give an idea of how machines over the reals tempered with condition, approximation, round-off, and probability enable us to combine tools and traditions of theoretical computer science with tools and traditions of numerical analysis to help better understand the nature and complexity of computation.

Studying computation over reals is important stuff. Computational omplexity theory cannot claim to be a definitive theory of computation if it has no language to express the vast array of numerical algorithms that operate on reals. Moreover, at least a few people seem to think that the inability of a Turing machine to represent non-discrete computations is a severe blow to the Church-Turing thesis. Whether this is plausible or not, a well developed theory of computing with reals would go a long way towards clarifying the matter.