** Next:** How do we measure
** Up:** Convex Polyhedron
** Previous:** How can one enumerate
** Contents**

##

What computer models are appropriate
for the polyhedral computation?

There are two important computational models, the unit cost RAM
(random access machine)
and the Turing machine. The essential difference is
that the Turing machine uses the binary representations
of numbers and the computational time is measured precisely
down to the number of (unit cost) bit operations.
I believe that the RAM model, in which
each elementary arithmetic operation takes a unit time
and each integer number takes a unit space,
is the standard model for the polyhedral computation.
This model, despite its simplicity, often illuminates
the critical parts of an algorithm and thus
reflects the actual computation well.
Of course, ignoring the number of bits
of a largest number arising in the computation is dangerous,
if one does not control the exponential growth of bit lengths of
the numbers (in terms of the input bit length). This warning should be
always kept in mind to design a good implementation.
Furthermore, there are certain cases in which
we need to use the Turing complexity.
For example, all known ``polynomial'' algorithms for the linear programming
(see Section 4) are Turing polynomial but not RAM polynomial.
We may avoid this problem by pretending that there were a RAM polynomial
algorithm for LP. After all, we (those interested in
geometric computation) are interested in an analysis
which reflects the reality and the simplex method for LP is
practically a RAM polynomial (or equivalently, strongly polynomial)
method.
We refer to the recent book [Yap00] for further discussions.

** Next:** How do we measure
** Up:** Convex Polyhedron
** Previous:** How can one enumerate
** Contents**
Komei Fukuda
2004-08-26