On the Computational Complexity of Approximating Solutions for Real Algebraic Formulae
1992; Society for Industrial and Applied Mathematics; Volume: 21; Issue: 6 Linguagem: Inglês
10.1137/0221060
ISSN1095-7111
Autores Tópico(s)Logic, programming, and type systems
ResumoPrevious article Next article On the Computational Complexity of Approximating Solutions for Real Algebraic FormulaeJames RenegarJames Renegarhttps://doi.org/10.1137/0221060PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstractUpper bounds on the complexity of approximating solutions of general algebraic formulae over the real numbers are established; included are systems of polynomial equations and inequalities.[1] Stuart J. Berkowitz, On computing the determinant in small parallel time using a small number of processors, Inform. Process. Lett., 18 (1984), 147–150 10.1016/0020-0190(84)90018-8 85k:65111 0541.68019 CrossrefISIGoogle Scholar[2] Allan Borodin, , Joachim von zur Gathen and , John Hopcroft, Fast parallel matrix and GCD computations, Inform. and Control, 52 (1982), 241–256 84j:68019 0507.68020 CrossrefGoogle Scholar[3] Lenore Blum, , Mike Shub and , Steve Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc. (N.S.), 21 (1989), 1–46 90a:68022 0681.03020 CrossrefISIGoogle Scholar[4] Lenore Blum and , Steve Smale, The Gödel incompleteness theorem and decidability over a ring, From Topology to Computation: Proceedings of the Smalefest (Berkeley, CA, 1990), Springer, New York, 1993, 321–339 96b:03056 0793.03066 Google Scholar[5] W. Brown and , J. Traub, On Euclid's algorithm and the theory of subresultants, J. Assoc. Comput. Mach., 18 (1971), 505–514 10.1145/321662.321665 46:2820 0226.65041 CrossrefISIGoogle Scholar[6] John Canny, The complexity of robot motion planning, ACM Doctoral Dissertation Awards, Vol. 1987, MIT Press, Cambridge, MA, 1988xviii+197 89m:68142 Google Scholar[7] A. L. Chistov and , D. Y. Grigor'ev, Subexponential time solving systems of algebraic equations, I and II, LOMI, E-9-83, E-10-83, Leningrad, preprint Google Scholar[8] George E. Collins, Quantifier elimination for real closed fields by cylindrical algebraic decompositionAutomata theory and formal languages (Second GI Conf., Kaiserslautern, 1975), Springer, Berlin, 1975, 134–183. Lecture Notes in Comput. Sci., Vol. 33 53:7771 0318.02051 CrossrefGoogle Scholar[9] L. Csanky, Fast parallel matrix inversion algorithms, SIAM J. Comput., 5 (1976), 618–623 10.1137/0205040 56:13549 0353.68063 LinkGoogle Scholar[10] M. Coste and , M. F. Roy, Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets, J. Symbolic Comput., 5 (1988), 121–129 89g:12002 0689.14006 CrossrefISIGoogle Scholar[11] D. Yu. Grigorev and , N. N. Vorobjov, Solving systems of polynomial inequalities in subexponential time, J. Symbolic Comput., 5 (1988), 37–64 89h:13001 0662.12001 CrossrefISIGoogle Scholar[12] D. Grigorev, Complexity of deciding Tarski algebra, J. Symbolic Comput., 5 (1988), 65–108 90b:03054 0689.03021 CrossrefISIGoogle Scholar[13] Joos Heintz, , M.-F. Roy and , Pablo Solernó, Sur la complexité du principe de Tarski-Seidenberg, Bull. Soc. Math. France, 118 (1990), 101–126 92g:03047 0767.03017 CrossrefISIGoogle Scholar[14] Peter Henrici, Applied and Computational Complex Analysis, Vol. 1, John Wiley, New York, 1974 0313.30001 Google Scholar[15] Daniel Lazard, Résolution des systèmes d'équations algébriques, Theoret. Comput. Sci., 15 (1981), 77–110 10.1016/0304-3975(81)90064-5 82i:12001 0459.68013 CrossrefISIGoogle Scholar[16] C. Andrew Neff, Specified precision polynomial root isolation is in NC, J. Comput. System Sci., 48 (1994), 429–463 95k:68080 0806.68054 CrossrefISIGoogle Scholar[17] James Renegar, On the worst-case arithmetic complexity of approximating zeros of polynomials, J. Complexity, 3 (1987), 90–113 89a:68107 0642.65031 CrossrefGoogle Scholar[18] James Renegar, On the worst-case arithmetic complexity of approximating zeros of systems of polynomials, SIAM J. Comput., 18 (1989), 350–370 10.1137/0218024 90j:68021 0676.65045 LinkISIGoogle Scholar[19] James Renegar, On the computational complexity and geometry of the first-order theory of the reals. I. Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals, J. Symbolic Comput., 13 (1992), 255–299 93h:03011a 0763.68042 CrossrefISIGoogle Scholar[20] James Renegar, On the computational complexity and geometry of the first-order theory of the reals. II. The general decision problem. Preliminaries for quantifier elimination, J. Symbolic Comput., 13 (1992), 301–327 93h:03011b 0763.68043 CrossrefISIGoogle Scholar[21] James Renegar, On the computational complexity and geometry of the first-order theory of the reals. III. Quantifier elimination, J. Symbolic Comput., 13 (1992), 329–352 93h:03011c 0798.68073 CrossrefISIGoogle Scholar[22] James Renegar, Recent progress on the complexity of the decision problem for the realsDiscrete and computational geometry (New Brunswick, NJ, 1989/1990), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol. 6, Amer. Math. Soc., Providence, RI, 1991, 287–308 93c:03055 0741.03004 CrossrefGoogle Scholar[23] Alfred Tarski, A decision method for elementary algebra and geometry, University of California Press, Berkeley and Los Angeles, Calif., 1951iii+63 13,423a 0044.25102 CrossrefGoogle Scholar[24] N. N. Vorobjov, Jr., Bounds of real roots of a system of algebraic equations, Notes of Sci. Seminars of Leningrad Dept. of Math. Steklov Inst., 137 (1984), 7–19 Google ScholarKeywordspolynomialsdecision methodsroots Previous article Next article FiguresRelatedReferencesCited ByDetails Complexity, exactness, and rationality in polynomial optimizationMathematical Programming, Vol. 19 | 16 May 2022 Cross Ref Quadratic convergence to the optimal solution of second-order conic optimization without strict complementarityOptimization Methods and Software, Vol. 34, No. 5 | 9 October 2018 Cross Ref Approximation schemes for r-weighted Minimization Knapsack problemsAnnals of Operations Research, Vol. 279, No. 1-2 | 6 December 2018 Cross Ref Weighted low rank approximations with provable guaranteesProceedings of the forty-eighth annual ACM symposium on Theory of Computing | 19 June 2016 Cross Ref An Almost Optimal Algorithm for Computing Nonnegative RankAnkur MoitraSIAM Journal on Computing, Vol. 45, No. 1 | 4 February 2016AbstractPDF (301 KB)Nonnegative Matrix FactorizationProceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation | 24 June 2015 Cross Ref On the Complexity of Nonlinear Mixed-Integer OptimizationMixed Integer Nonlinear Programming | 15 November 2011 Cross Ref Nonlinear Integer Programming50 Years of Integer Programming 1958-2008 | 6 November 2009 Cross Ref FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimensionMathematical Programming, Vol. 115, No. 2 | 1 September 2007 Cross Ref Approximation Classes for Real Number Optimization ProblemsUnconventional Computation | 1 Jan 2006 Cross Ref Analytical solutions to the optimization of a quadratic cost function subject to linear and quadratic equality constraintsApplied Mathematics & Optimization, Vol. 34, No. 2 | 1 Sep 1996 Cross Ref Ill-Posed Problem InstancesFrom Topology to Computation: Proceedings of the Smalefest | 1 Jan 1993 Cross Ref On the computational complexity and geometry of the first-order theory of the reals. Part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the realsJournal of Symbolic Computation, Vol. 13, No. 3 | 1 Mar 1992 Cross Ref Computing integral points in convex semi-algebraic setsProceedings 38th Annual Symposium on Foundations of Computer Science Cross Ref Volume 21, Issue 6| 1992SIAM Journal on Computing1001-1198 History Submitted:23 October 1989Accepted:15 August 1991Published online:13 July 2006 InformationCopyright © 1992 Society for Industrial and Applied MathematicsKeywordspolynomialsdecision methodsrootsMSC codes656890PDF Download Article & Publication DataArticle DOI:10.1137/0221060Article page range:pp. 1008-1025ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics
Referência(s)