Saturation and stability in the theory of computation over the reals

Annals of Pure and Applied Logic 99 (1-3):1-49 (1999)
  Copy   BIBTEX

Abstract

This paper was motivated by the following two questions which arise in the theory of complexity for computation over ordered rings in the now famous computational model introduced by Blum, Shub and Smale: 1. is the answer to the question P = ?NP the same in every real-closed field?2. if P ≠ NP for , does there exist a problem of which is NP but neither P nor NP-complete ?Some unclassical complexity classes arise naturally in the study of these questions. They are still open, but we could obtain unconditional results of independent interest.Michaux introduced/const complexity classes in an effort to attack question . We show that , answering a question of his. Here A is the class of real problems which are algorithmic in bounded time. We also prove the stronger result: , where PAR stands for parallel polynomial time. In our terminology, we say that is A-saturated and PAR-saturated. We also prove, at the nonuniform level, the above results for every real-closed field. It is not known whether is P-saturated. In the case of the reals with addition and order we obtain P-saturation ). More generally, we show that an ordered -vector space is P-saturated at the nonuniform level ).We also study a stronger notion that we call P-stability. Blum, Cucker, Shub and Smale have shown that fields of characteristic 0 are P-stable. We show that the reals with addition and order are P-stable, but real-closed fields are not.Questions and and the/const complexity classes have some model theoretic flavor. This leads to the theory of complexity over “arbitrary” structures as introduced by Poizat. We give a summary of this theory with a special emphasis on the connections with model theory and we study/const complexity classes from this point of view. Note also that our proof of the PAR-saturation of shows that an o-minimal structure which admits quantifier elimination is A-saturated at the nonuniform level

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Saturation, Suslin trees and meager sets.Paul Larson - 2005 - Archive for Mathematical Logic 44 (5):581-595.
Recursive Approximability of Real Numbers.Xizhong Zheng - 2002 - Mathematical Logic Quarterly 48 (S1):131-156.
On the constructive Dedekind reals.Robert S. Lubarsky & Michael Rathjen - 2008 - Logic and Analysis 1 (2):131-152.
Accessible telephone directories.John B. Goode - 1994 - Journal of Symbolic Logic 59 (1):92-105.
Cohen reals from small forcings.Janusz Pawlikowski - 2001 - Journal of Symbolic Logic 66 (1):318-324.
Bounded Scott Set Saturation.Alex M. McAllister - 2002 - Mathematical Logic Quarterly 48 (2):245-259.
Logics which capture complexity classes over the reals.Felipe Cucker & Klaus Meer - 1999 - Journal of Symbolic Logic 64 (1):363-390.
Mapping a set of reals onto the reals.Arnold W. Miller - 1983 - Journal of Symbolic Logic 48 (3):575-584.
Subclasses of the Weakly Random Reals.Johanna N. Y. Franklin - 2010 - Notre Dame Journal of Formal Logic 51 (4):417-426.
Regular reals.Guohua Wu - 2005 - Mathematical Logic Quarterly 51 (2):111-119.

Analytics

Added to PP
2014-01-16

Downloads
16 (#774,858)

6 months
1 (#1,042,085)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Stabilité polynômiale Des corps différentiels.Natacha Portier - 1999 - Journal of Symbolic Logic 64 (2):803-816.

Add more citations

References found in this work

Definable types in o-minimal theories.David Marker & Charles I. Steinhorn - 1994 - Journal of Symbolic Logic 59 (1):185-198.
Definable Types in $mathscr{O}$-Minimal Theories.David Marker & Charles I. Steinhorn - 1994 - Journal of Symbolic Logic 59 (1):185-198.
Tame Topology and O-Minimal Structures.Lou van den Dries - 2000 - Bulletin of Symbolic Logic 6 (2):216-218.
Accessible telephone directories.John B. Goode - 1994 - Journal of Symbolic Logic 59 (1):92-105.

View all 7 references / Add more references