Solving systems of polynomial inequalities in subexponential time
From MaRDI portal
algebraic complexityreal solutions of systems of polynomial inequalitiessubexponential time algorithm
Polynomials (irreducibility, etc.) (11R09) Software, source code, etc. for problems pertaining to field theory (12-04) Fields related with sums of squares (formally real fields, Pythagorean fields, etc.) (12D15) Real algebraic and real-analytic geometry (14Pxx) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)
The authors developed a subexponential time algorithm to find real solutions of systems of polynomial inequalities. A method of finding real roots of a polynomial was introduced as a starting point of the algorithm and the general case was reduced to this case. Theoretical background of the algorithm was given in details in the paper while a general outline of the algorithm was provided. The algorithm has a running time bounded by \(M(kd)^{n^ 2}\), where k is the number of polynomials with degrees less than d and coefficients not exceeding \(2^ M\), n is the number of the variables. The previously known upper bound for this problem was \((Mkd)^{2^{O(n)}}\).
Recommendations
Cites work
- An Inequality About Factors of Polynomials
- Definability and fast quantifier elimination in algebraically closed fields
- scientific article; zbMATH DE number 3870491 (Why is no real title available?)
- scientific article; zbMATH DE number 3906595 (Why is no real title available?)
- scientific article; zbMATH DE number 3959582 (Why is no real title available?)
- scientific article; zbMATH DE number 3982411 (Why is no real title available?)
- scientific article; zbMATH DE number 4092769 (Why is no real title available?)
- scientific article; zbMATH DE number 3497890 (Why is no real title available?)
- scientific article; zbMATH DE number 3564960 (Why is no real title available?)
- scientific article; zbMATH DE number 3627912 (Why is no real title available?)
- scientific article; zbMATH DE number 3637614 (Why is no real title available?)
- scientific article; zbMATH DE number 3804835 (Why is no real title available?)
- scientific article; zbMATH DE number 3445379 (Why is no real title available?)
- scientific article; zbMATH DE number 3893304 (Why is no real title available?)
- scientific article; zbMATH DE number 3893305 (Why is no real title available?)
- scientific article; zbMATH DE number 3895043 (Why is no real title available?)
- scientific article; zbMATH DE number 3221041 (Why is no real title available?)
- scientific article; zbMATH DE number 3307642 (Why is no real title available?)
- scientific article; zbMATH DE number 3068536 (Why is no real title available?)
- Integer Arithmetic Algorithms for Polynomial Real Zero Determination
- On the Betti Numbers of Real Varieties
Cited in
(only showing first 100 items - show all)- On the number of topological types occurring in a parameterized family of arrangements
- Condition number based complexity estimate for computing local extrema
- A bibliography of quantifier elimination for real closed fields
- 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
- 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
- The complexity of deciding consistency of systems of polynomials in exponent inequalities
- Counting connected components of a semialgebraic set in subexponential time
- Complexity of deciding Tarski algebra
- An algorithm for sums of squares of real polynomials
- Complexity of computing the local dimension of a semialgebraic set
- Construction of roadmaps in semi-algebraic sets
- Description of the connected components of a semialgebraic set in single exponential time
- Finding irreducible components of some real transcendental varieties
- Polar varieties, real equation solving, and data structures: the hypersurface case
- Complexity lower bounds for computation trees with elementary transcendental function gates
- A lower bound for randomized algebraic decision trees
- Randomization and the computational power of analytic and algebraic decision trees
- Grid methods in computational real algebraic (and semialgebraic) geometry
- Matrices in elimination theory
- Real solving for positive dimensional systems.
- Un procédé d'élimination effective et quelques applications. (A procedure for effective elimination and some applications.)
- Complexity of stratifications of semi-Pfaffian sets
- Numerically computing real points on algebraic sets
- Deformation techniques for efficient polynomial equation solving.
- On exact Reznick, Hilbert-Artin and Putinar's representations
- Efficiently and effectively recognizing toricity of steady state varieties
- Techniques and results on approximation algorithms for packing circles
- Bit complexity for computing one point in each connected component of a smooth real algebraic set
- Smooth points on semi-algebraic sets
- Cooperating techniques for solving nonlinear real arithmetic in the \texttt{cvc5} SMT solver (system description)
- When a system of real quadratic equations has a solution
- An approximate characterisation of the set of feasible trajectories for constrained flat systems
- Real root finding for low rank linear matrices
- Links with splitting number one
- Intrinsic complexity estimates in polynomial optimization
- On the geometry of polar varieties
- Identifying the parametric occurrence of multiple steady states for some biological networks
- Computing the homology of semialgebraic sets. I: Lax formulas
- Segment representations with small resolution
- Feasibility testing for systems of real quadratic equations
- Generalized polar varieties: geometry and algorithms
- A PTAS for the disk cover problem of geometric objects
- Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
- Minimizing polynomials via sum of squares over the gradient ideal
- 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
- Systole length in hyperbolic \(n\)-manifolds
- Computing a nonnegative matrix factorization -- provably
- A survey of satisfiability modulo theory
- Exact algorithms for linear matrix inequalities
- Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity
- Solving polynomial equations in smoothed polynomial time and a near solution to Smale's 17th problem
- MRHS Equation Systems that can be Solved in Polynomial Time
- The number of bits needed to represent a unit disk graph
- Polynomial-time approximation schemes for circle and other packing problems
- A polynomial-time algorithm for computing low CP-rank decompositions
- Semidefinite approximations of projections and polynomial images of semialgebraic sets
- Recent advances in real geometric reasoning
- scientific article; zbMATH DE number 4157784 (Why is no real title available?)
- Practical and Theoretical Issues for the Computation of Generalized Critical Values of a Polynomial Mapping
- Combined Decision Techniques for the Existential Theory of the Reals
- scientific article; zbMATH DE number 3982411 (Why is no real title available?)
- scientific article; zbMATH DE number 16666 (Why is no real title available?)
- Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces
- Sur la complexité du principe de Tarski-Seidenberg
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- Exponentially more concise quantum recognition of non-RMM regular languages
- scientific article; zbMATH DE number 4119512 (Why is no real title available?)
- Proving inequalities and solving global optimization problems via simplified CAD projection
- On the recognition of unit disk graphs and the distance geometry problem with ranges
- Learning time dependent choice
- An elementary recursive bound for effective Positivstellensatz and Hilbert's 17th problem
- Bounds on the number of connected components for tropical prevarieties
- Fixed points, Nash equilibria, and the existential theory of the reals
- Elementary recursive quantifier elimination based on Thom encoding and sign determination
- The complexity of positive semidefinite matrix factorization
- Generalized polar varieties and an efficient real elimination.
- Computing Amoebas
- Centerpoints: a link between optimization and convex geometry
- 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
- The real computational complexity of minmax value and equilibrium refinements in multi-player games
- Finding at least one point in each connected component of a real algebraic set defined by a single equation
- Decomposition plans for geometric constraint systems. I: Performance measures for CAD
- Complexity of cylindrical decompositions of sub-Pfaffian
- Computational complexity of quantifier-free negationless theory of field of rational numbers
- Cylindrical algebraic decomposition using local projections
- Finding connected components of a semialgebraic set in subexponential time
- Sublinear P system solutions to NP-complete problems
- Stability analysis of a bacterial growth model through computer algebra
- Bounding the radii of balls meeting every connected component of semi-algebraic sets
- Conormal spaces and Whitney stratifications
- Faster real root decision algorithm for symmetric polynomials
- The complexity of the Hausdorff distance
- RAC-Drawability is ∃ℝ-complete and Related Results
This page was built for publication: Solving systems of polynomial inequalities in subexponential time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1113939)
