Solving systems of polynomial inequalities in subexponential time

DOI10.1016/S0747-7171(88)80005-1zbMath0662.12001MaRDI QIDQ1113939

Nikolaj N. jun. Vorob'ev, Dima Yu. Grigoriev

Publication date: 1988

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

zbMATH Keywords

algebraic complexityreal solutions of systems of polynomial inequalitiessubexponential time algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Fields related with sums of squares (formally real fields, Pythagorean fields, etc.) (12D15) Polynomials (irreducibility, etc.) (11R09) Real algebraic and real-analytic geometry (14Pxx) Software, source code, etc. for problems pertaining to field theory (12-04)

Related Items (only showing first 100 items - show all)

Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients ⋮ On the Complexity of Equilibrium Computation in First-Price Auctions ⋮ An algorithmic approach to Rupert’s problem ⋮ Finding irreducible components of some real transcendental varieties ⋮ Feasibility testing for systems of real quadratic equations ⋮ Semidefinite Approximations of Projections and Polynomial Images of SemiAlgebraic Sets ⋮ Recent Advances in Real Geometric Reasoning ⋮ Un procédé d'élimination effective et quelques applications. (A procedure for effective elimination and some applications.) ⋮ When a system of real quadratic equations has a solution ⋮ Complexity of stratifications of semi-Pfaffian sets ⋮ A potential reduction algorithm for two-person zero-sum mean payoff stochastic games ⋮ Computing final polynomials and final syzygies using Buchberger's Gröbner bases method ⋮ Polynomial-time approximation schemes for circle and other packing problems ⋮ A bibliography of quantifier elimination for real closed fields ⋮ Generalized polar varieties: geometry and algorithms ⋮ Polar varieties, real equation solving, and data structures: the hypersurface case ⋮ A polynomial-time algorithm for computing low CP-rank decompositions ⋮ Complexity lower bounds for computation trees with elementary transcendental function gates ⋮ Oscillation of linear ordinary differential equations: on a theorem of A. Grigoriev ⋮ An approximate characterisation of the set of feasible trajectories for constrained flat systems ⋮ Real root finding for low rank linear matrices ⋮ Bounding the radii of balls meeting every connected component of semi-algebraic sets ⋮ A lower bound for randomized algebraic decision trees ⋮ Randomization and the computational power of analytic and algebraic decision trees ⋮ Systole length in hyperbolic \(n\)-manifolds ⋮ Involutions of polynomially parametrized surfaces ⋮ The Complexity of Positive Semidefinite Matrix Factorization ⋮ An Elementary Recursive Bound for Effective Positivstellensatz and Hilbert’s 17th problem ⋮ Condition number based complexity estimate for solving polynomial systems ⋮ Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces ⋮ Nonrealizability proofs in computational geometry ⋮ Numerically computing real points on algebraic sets ⋮ Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem ⋮ A PTAS for the disk cover problem of geometric objects ⋮ Exponentially more concise quantum recognition of non-RMM regular languages ⋮ Smoothing of real algebraic hypersurfaces by rigid isotopies ⋮ The complexity of point configurations ⋮ Computational algebraic geometry of projective configurations ⋮ Recent improvements in the complexity of the effective Nullstellensatz ⋮ A singly exponential stratification scheme for real semi-algebraic varieties and its applications ⋮ Links with splitting number one ⋮ Deformation techniques for efficient polynomial equation solving. ⋮ Proving inequalities and solving global optimization problems via simplified CAD projection ⋮ 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 ⋮ On the recognition of unit disk graphs and the distance geometry problem with ranges ⋮ The complexity of deciding consistency of systems of polynomials in exponent inequalities ⋮ Lower bound on testing membership to a polyhedron by algebraic decision and computation trees ⋮ Bounds on the number of connected components for tropical prevarieties ⋮ Deciding consistency of systems of exponential-polynomial inequalities in subexponential time ⋮ Fixed points, Nash equilibria, and the existential theory of the reals ⋮ A numerical algorithm for zero counting. I: Complexity and accuracy ⋮ Grid methods in computational real algebraic (and semialgebraic) geometry ⋮ Finding at least one point in each connected component of a real algebraic set defined by a single equation ⋮ Intrinsic complexity estimates in polynomial optimization ⋮ Elementary recursive quantifier elimination based on Thom encoding and sign determination ⋮ Polynomial bounds for the oscillation of solutions of Fuchsian systems ⋮ The real computational complexity of minmax value and equilibrium refinements in multi-player games ⋮ Counting connected components of a semialgebraic set in subexponential time ⋮ Centerpoints: A Link between Optimization and Convex Geometry ⋮ Decomposition plans for geometric constraint systems. I: Performance measures for CAD ⋮ Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets ⋮ Minimizing polynomials via sum of squares over the gradient ideal ⋮ On the geometry of polar varieties ⋮ Practical and Theoretical Issues for the Computation of Generalized Critical Values of a Polynomial Mapping ⋮ Complexity of cylindrical decompositions of sub-Pfaffian ⋮ Unnamed Item ⋮ The Number of Bits Needed to Represent a Unit Disk Graph ⋮ On the intrinsic complexity of point finding in real singular hypersurfaces ⋮ On exact Reznick, Hilbert-Artin and Putinar's representations ⋮ Computational complexity of quantifier-free negationless theory of field of rational numbers ⋮ Identifying the parametric occurrence of multiple steady states for some biological networks ⋮ Some lower bounds for the complexity of the linear programming feasibility problem over the reals ⋮ Efficiently and effectively recognizing toricity of steady state varieties ⋮ Cylindrical algebraic decomposition using local projections ⋮ Computing the homology of semialgebraic sets. I: Lax formulas ⋮ On the number of topological types occurring in a parameterized family of arrangements ⋮ Matrices in elimination theory ⋮ Complexity of deciding Tarski algebra ⋮ Computing a Nonnegative Matrix Factorization---Provably ⋮ Computing Amoebas ⋮ Sur la complexité du principe de Tarski-Seidenberg ⋮ Combined Decision Techniques for the Existential Theory of the Reals ⋮ Condition number based complexity estimate for computing local extrema ⋮ A Survey of Satisfiability Modulo Theory ⋮ Unnamed Item ⋮ Finding connected components of a semialgebraic set in subexponential time ⋮ Exact Algorithms for Linear Matrix Inequalities ⋮ On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines ⋮ Techniques and results on approximation algorithms for packing circles ⋮ An algorithm for sums of squares of real polynomials ⋮ Complexity of computing the local dimension of a semialgebraic set ⋮ Segment representations with small resolution ⋮ Bit complexity for computing one point in each connected component of a smooth real algebraic set ⋮ Smooth points on semi-algebraic sets ⋮ Construction of roadmaps in semi-algebraic sets ⋮ Cooperating techniques for solving nonlinear real arithmetic in the \texttt{cvc5} SMT solver (system description) ⋮ Solving systems of polynomial inequalities over a real closed field in subexponential time ⋮ Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity ⋮ Description of the connected components of a semialgebraic set in single exponential time ⋮ Real solving for positive dimensional systems.

Cites Work

• Definability and fast quantifier elimination in algebraically closed fields
• An Inequality About Factors of Polynomials
• Integer Arithmetic Algorithms for Polynomial Real Zero Determination
• On the Betti Numbers of Real Varieties
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Solving systems of polynomial inequalities in subexponential time