zbMATH — the first resource for mathematics

P\(\neq\)NP over the nonstandard reals implies P\(\neq\)NP over \(\mathbb{R}\). (English) Zbl 0822.68033
Summary: L. Blum, M. Shub and S. Smale [Bull. Am. Math. Soc. 21, No. 1, 1-46 (1989; Zbl 0681.03020)] showed the existence of a NP-complete problem over the real closed fields in the framework of their theory of computation over the reals. This allows to ask for the P\(\neq\)NP question over real close fields. Here we show that P\(\neq\)NP over a real closed extension of the reals implies P\(\neq\)NP over the reals. We also discuss the converse. This leads to define some subclasses of P/poly. Finally we show that the transfer result about P\(\neq\)NP is a part of a very abstract result.

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
12L15 Nonstandard arithmetic and field theory
Full Text: DOI
[1] Barwise, K.J.; Schlipf, J., An introduction to recursively saturated and replendent models, J. symbolic logic, 41, 2, 531-536, (1976) · Zbl 0343.02032
[2] Blum, L.; Shub, M.; Smale, S., On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. amer. math. soc., 21, 1-46, (1989) · Zbl 0681.03020
[3] Chang, C.C.; Keisler, H.J., Model theory, (1990), North-Holland Amsterdam · Zbl 0697.03022
[4] Friedman, H.; Mansfield, R., Algorithmic procedures, Trans amer. math soc., 332, 1, 297-312, (1992) · Zbl 0774.03030
[5] Goode, J.B., Accessible telephone directories, J. symbolic logic, 59, 92-105, (1994) · Zbl 0804.03028
[6] Keisler, H.J., Constructions in model theory, Proc. centro internazionale matematico estivo, 56-108, (1975)
[7] Maass, W., On the use of inaccessible numbers and order indiscernibles in lower bound arguments for random access machines, J. symbolic logic, 53, 4, 1098-1109, (1988) · Zbl 0683.03021
[8] Megiddo, N., A general NP-completeness theorem, (), 432-442 · Zbl 0815.68055
[9] Michaux, C., Bornes inférieures en théorie de la complexite, ()
[10] Renegar, J., On the computational complexity and geometry of the first-order of the reals, I, II, III, J. symbolic comput., 13, 255-352, (1992) · Zbl 0798.68073
[11] Sacks, G.E., Saturated model theory, (1972), Benjamin New York · Zbl 0242.02054
[12] van den Dries, L., Alfred Tarski’s elimination theory for real closed fields, J. symbolic logic, 53, 1, 7-19, (1988) · Zbl 0651.03001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.