[ Pobierz całość w formacie PDF ]
BULLETIN (New Series) OF THE
AMERICAN MATHEMATICAL SOCIETY
Volume 21, Number 1, July 1989
ON A THEORY OF COMPUTATION AND COMPLEXITY
OVER THE REAL NUMBERS: NP-COMPLETENESS,
RECURSIVE FUNCTIONS AND UNIVERSAL MACHINES
1
LENORE BLUM
2
, MIKE SHUB AND STEVE SMALE
ABSTRACT. We present a model for computation over the reals or an
arbitrary (ordered) ring
R.
In this general setting, we obtain universal
machines, partial recursive functions, as well as JVP-complete problems.
While our theory reflects the classical over Z (e.g., the computable func-
tions are the recursive functions) it also reflects the special mathematical
character of the underlying ring
R
(e.g., complements of Julia sets provide
natural examples of R. E. undecidable sets over the reals) and provides
a natural setting for studying foundational issues concerning algorithms
in numerical analysis.
Introduction.
We develop here some ideas for machines and computa-
tion over the real numbers R.
One motivation for this comes from scientific computation. In this use
of the computer, a reasonable idealization has the cost of multiplication
independent of the size of the number. This contrasts with the usual
theoretical computer science picture which takes into account the number
of bits of the numbers.
Another motivation is to bring the theory of computation into the do-
main of analysis, geometry and topology. The mathematics of these sub-
jects can then be put to use in the systematic analysis of algorithms.
On the other hand, there is an extensively developed subject of the
theory of discrete computation, which we don't wish to lose in our theory.
Toward this end we define machines, partial recursive functions, and other
objects of study over a ring
R.
Then in the case where
R
is the ring of
integers Z, we have the same objects (or perhaps equivalent objects) as the
classical ones. Computable functions over Z are thus ordinary computable
functions. R.E. sets over Z are ordinary R.E. sets. But when the ring is
specialized to the real numbers, we have computable functions which are
reasonable for the study of algorithms of numerical analysis. R.E. sets over
R are no longer countable and include, for example, basins of attraction
of complex analytic dynamical systems.
Received by the editors April 21, 1988.
1980
Mathematics Subject Classification
(1985
Revision).
Primary 03D15, 68Q15; Sec-
ondary 65V05.
1
Partially supported by NSF grants. Some of this work was done while Blum and Smale
were visiting Shub at the IBM, T. J. Watson Research Center.
2
Partially supported by the Letts-Villard Chair at Mills College and the International
Computer Science Institute, Berkeley.
© 1989 American Mathematical Society
0273-0979/89 $1.00 + $.25 per page
1
2
LENORE BLUM, MIKE SHUB AND STEVE SMALE
There is another virtue of developing a theory of machines over a ring.
It forces a more algebraic approach, closer to classical mathematics, than
the approach from logic.
Here is an abbreviated description of some of the results of this paper,
in this context of machines over a ring
R.
(I) Most Julia sets are not R.E. over the reals, so their
complements, the basins of attraction, provide natural ex-
amples of R.E.
undecidable sets
over R (§§1 and 10).
The Julia set example provides an interesting link between the theory
of computation and dynamical systems. A perhaps deeper link is the
com-
puting endomorphism
(§3) which is an important conceptual and technical
tool used in our development.
(II) An analogue of Cook's JVP-completeness theorem is
proved over the real numbers. The
NP-complete prob-
lem
over R is the
4-Feasibility problem,
i.e. the prob-
lem of deciding whether or not a real degree 4 polynomial
ƒ : R" -> R has a zero (§6).
This result, in addition to focusing attention on the 4-Feasibility prob-
lem over R has some interesting consequences which point to the
subtle
differences
between the theories of
NP
over R and over Z. For example,
by straightforward counting arguments, any NP-problem over Z is seen
to be solvable in 2
poly(w
)
time. (See e.g.
Garey-Johnson.)
An analogous
result over the reals is far from obvious since there are a continuum of
possible guesses over R. It is not even clear
a priori
that AT-problems
over R are decidable. However, since the 4-Feasibility problem over R is
decidable (by
Tarski-Seidenberg)
and since the current best upper bound
for decidability of the existential theory of the reals is
4°^
(see
Renegar,
also
Canny
and
Grigorev-Vorobjov),
we also get exponential upper bounds
for TVP-problems over R but for much deeper reasons than the case over
Z. For another interesting difference between the two theories, note that
by Hilbert's Tenth Problem, the 4-Feasibility problem restated over Z is
not
even decidable over Z and so
not
in
NP
over Z.
PROBLEM.
What is the relation between the problems
P
=
NP
over R,
and
P = NP
over Z?
(III) Computable functions over
R
are characterized in-
trinsically by a class we call
partial recursive functions
over
R.
For JR = Z, these are the usual partial recursive func-
tions (§7).
(IV) There exists a
universal machine
over
R.
This ma-
chine, inspired by the Universal Turing Machine, does the
computation of any machine over
R.
The universal ma-
chine over
R
turns out to be independent of
R.
Moreover,
by avoiding Gödel coding via prime numbers, the algebraic
structure of the universal machine remains intact (§8).
NP-COMPLETENESS, RECURSIVE FUNCTIONS AND UNIVERSAL MACHINES
3
(V) Inspired by the work of Davis, Robinson and Put-
nam, and Matijasèvic on Hubert's tenth problem, we give
a "diophantine-like" description of R.E. sets, for a certain
class of machines (§9).
There are a large number of contributions of mathematicians and com-
puter scientists which predate and relate to this work. A very brief survey,
with some comparisons, follows.
Of course, the work of Turing, Gödel, Church and others in the thirties
forms the core of the existing framework for our work. Although much of
the classical theory of computation deals with computing over the natural
numbers, certain approaches have considered other underlying domains.
Close to the classical approach,
Rabin
developed a theory of computable
algebra and fields in which the underlying domains can be effectively coded
by natural numbers and are thus, necessarily countable.
On the other hand, the theories of computation over abstract structures,
are perhaps more general than ours. See e.g.,
Friedman
(or as discussed
by Shepherdson in
Harrington, et al), Tiuryn,
and
Moschovakis.
These
general approaches both exploit and explore the logical properties of pro-
cedures. But, when applied to specific structures such as the reals, they
do not yield the concrete mathematical results (e.g. about Julia sets or the
4-Feasibility problem) that quite naturally follow from the more mathe-
matical model developed in this paper.
Recursive analysis provides yet another approach. See,
e.g. Friedman-
Ko, Pour-El-Richards, Hoover and Kreitz-Weihrauch.
Some tools here are
recursive functionals, computable real numbers and oracle Turing ma-
chines where, roughly, one imagines a real number fed to the machine
bit by bit. To contrast, we view a real number not as its decimal (or
binary) expansion, but rather a mathematical entity as is generally the
practice in numerical analysis. Thus, for example, we suppose Newton's
algorithm for finding the zeroes of a polynomial ƒ to be performed on an
arbitrary real, not just a computable real; the fundamental components
of the algorithm in our model, as in practice, are the rational operations
Nf{x) = x
-
f(x)/f'(x),
not the bit operations.
The development of algebraic complexity theory, in particular the work
of Ostrowski,
Pan, Winograd, Strassen and Schönhage
(see
von zur Gathen
for a recent survey) gave rise to the "real number model" approach to com-
putation. Decision and computation tree models as in
Rabin, Steele-Yao,
Ben-Or,
and the tame machines in
Smale,
are such real number models
of computation but considerably less powerful or general purpose than
ours (e.g., they have bounded halting time and none are universal; also
they don't allow for uniform algorithms as do our infinite dimensional
machines).
More closely related are the register machines of
Shepherdson-Sturgis
and the RAM's or random access machines. (See
Aho-Hopcroft-Ullman
or
Machtey-Young
for discrete versions.) While a definition of a real RAM
is given in
Preparata-Shamos,
the formal development of a theory is not
4
LENORE BLUM, MIKE SHUB AND STEVE SMALE
pursued. Indeed, in their book, only a subclass of machines, equivalent
to the class of decision trees, is utilized. Perhaps closest to our approach
is the work of
Herman-hard
on computability over arbitrary fields. Also
close in spirit is a theory of real Turing machines outlined by
Abramson.
Nimrod Megiddo has also considered an example of an
N
P-complete over
R in our model.
Some other related papers are
Borodin, Valiant, Endler, Lovdsz,
and
Eaves-Rothblum
and
Traub- Wozniakowski.
Books having significant con-
tact with this paper include
Davis, Eilenberg, Manin, Manna, Minsky
and
Rogers.
Especially in §§5 and 6 below, the influence of complexity work of Cook
and Karp (see
Garey-Johnson)
among many others, is evident. In our §8,
Robinson, Matijasèvic, Davis, and Putnam,
and
DenefhavG
been influen-
tial.
We would like to acknowledge helpful discussions with Martin Davis
and Steve Simpson.
Sections
1. Examples of machines over
R
2. Machines over a ring
R
3. The computing endomorphism and the register equations
4. Time
T
halting sets, equations, polynomials and computations
5. Complexity theory of machines over
R
6. TVP-completeness and the analogue to Cook's theorem over R
7. Computable functions, normal forms and partial recursive functions
over
R
8. Existence of a universal machine over a ring
9. Characterizing R.E. sets as output sets and pseudo-Diophantine sets
10. Most Julia sets are undecidable
11. Some final remarks and problems
References
1. Examples of machines over
R.
Even before defining our notion of
a machine, we give some examples. The first examples are related to the
theory of complex dynamical systems. We present them in some detail.
EXAMPLE
1. Consider a complex polynomial map
g
: C —• C. This map
g
will be considered as an endomorphism, mapping C into itself. Thus it
makes sense to iterate it. That is
g(g(z))
=
g
2
(z)
is defined as well as the
A:th iterate
g
k
(z),
for each
z e
C.
LEMMA.
There is a real constant, C
=
C
g
such that if\z\ > C, then
\g
k
(z)\ —
• oo
as k
—• oo.
This is true because the highest order term of a polynomial dominates
the others for
\z\
sufficiently large. Moreover, if
go(z) = z
à
,
\g§{z)\ =
\zf.
Now we may define a "machine"
M
from
g,
by the following flow chart
(see Figure 1).
This M is a machine over R, not C, since it uses the real comparison
\z\ < C
g
\
in the context of this machine, we view C as R
2
.
^-COMPLETENESS, RECURSIVE FUNCTIONS AND UNIVERSAL MACHINES
5
Input
ziC
Compute
g{z)
and
replace
z
by
g(z)
1*1 s
C.
\z\ < C
g
Output
z
FIGURE 1
One can see that the "halting set"
QM
of the machine
M
is precisely
the set of points which eventually tend to oo under iterates of
g.
The
halting set is analogous to the R.E. sets of recursive function theory, and
eventually we will define a class of machines which contains not only this
g
machine, but machines equivalent to Turing machines as well. Thus we
call QM an R.E. set over R. Note that it is certainly not a usual R.E. set
since it is not countable. It is natural to ask, is
QM
"decidable" or, inspired
by the classical tradition, is the complement of
Q,M
the halting set of some
other machine over R?
3
Of course at this point, not even having a definition of a machine over
R, the question can't be answered. But later we will show
PROPOSITION
I. Any R.E. set over
R
is the countable union of basic semi-
algebraic sets.
Here a basic
semialgebraic
set is a subset of Cartesian space
R
n
defined
by a set of polynomial inequalities of the form
hj(x)
< 0, / = 1,...,/,
hj(x)
<0, 7 = /+l,...,m.
A general reference for semialgebraic sets is
Becker.
Using this proposition, we answer our question in the next example for
a class of halting sets
£l
M
>
3
If the complement of
QM
is the halting set of some other machine
M\
we can construct
a machine to decide for each z G C "Is z € Œ^?" schematically as follows (see Figure 2).
Input
"Parallel process"
if .tf' halts
Output
Yes
if
M
halts
FIGURE 2
[ Pobierz całość w formacie PDF ]