ON THE COMPUTATIONAL-COMPLEXITY AND GEOMETRY OF THE 1ST-ORDER THEORY OF THE REALS .1. INTRODUCTION - PRELIMINARIES - THE GEOMETRY OF SEMI-ALGEBRAIC SETS - THE DECISION PROBLEM FOR THE EXISTENTIAL THEORY OF THE REALS

被引：134

作者：

RENEGAR, J

机构：

[1] School of Operations Research and Industrial Engineering, College of Engineering, Cornell University, Ithaca, New York

来源：

JOURNAL OF SYMBOLIC COMPUTATION | 1992年 / 13卷 / 03期

关键词：

D O I：

10.1016/S0747-7171(10)80003-3

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This series of papers presents a complete development and complexity analysis of a decision method, and a quantifier elimination method, for the first order theory of the reals. The complexity upper bounds which are established are the best presently available, both for sequential and parallel computation, and both for the bit model of computation and the real number model of computation; except for the bounds pertaining to the sequential decision method in the bit model of computation, all bounds represent significant improvements over previously established bounds. © 1992, Academic Press Limited. All rights reserved.

引用

页码：255 / 299

页数：45

共 33 条

[1] A BIBLIOGRAPHY OF QUANTIFIER ELIMINATION FOR REAL CLOSED FIELDS [J].

ARNON, DS .

JOURNAL OF SYMBOLIC COMPUTATION, 1988, 5 (1-2) :267-274

[2] THE COMPLEXITY OF ELEMENTARY ALGEBRA AND GEOMETRY [J].

BENOR, M ;

KOZEN, D ;

REIF, J .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1986, 32 (02) :251-264

[3] ON A THEORY OF COMPUTATION AND COMPLEXITY OVER THE REAL NUMBERS - NP-COMPLETENESS, RECURSIVE FUNCTIONS AND UNIVERSAL MACHINES [J].

BLUM, L ;

SHUB, M ;

SMALE, S .

BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1989, 21 (01) :1-46

[4]

BLUM L, 1992, TOPOLOGY COMPUTATION

[5] GENERALIZED CHARACTERISTIC-POLYNOMIALS [J].

CANNY, J .

JOURNAL OF SYMBOLIC COMPUTATION, 1990, 9 (03) :241-250

[6]

CHISTOV AL, 1984, LECT NOTES COMPUT SC, V176, P17

[7] DECISION PROCEDURES FOR REAL AND P-ADIC FIELDS [J].

COHEN, PJ .

COMMUNICATIONS ON PURE AND APPLIED MATHEMATICS, 1969, 22 (02) :131-&

[8]

COLLINS G, 1975, LECT NOTES COMPUT SC, V33, P134, DOI [DOI 10.1007/3-540-07407-4_17, 10.1007/3-540-07407-4_17]

[9]

Csanky L., 1976, SIAM Journal on Computing, V5, P618, DOI 10.1137/0205040

[10] PRECISE SEQUENTIAL AND PARALLEL COMPLEXITY-BOUNDS FOR QUANTIFIER ELIMINATION OVER ALGEBRAICALLY CLOSED FIELDS [J].

FITCHAS, N ;

GALLIGO, A ;

MORGENSTERN, J .

JOURNAL OF PURE AND APPLIED ALGEBRA, 1990, 67 (01) :1-14

← 1 2 3 4 →