The complexity of linear problems in fields
From MaRDI portal
Complexity bounds for decision problems) for linear sentences (that means that in atomic subformulas only linear polynomials occur) over different types of fields are established. It is proved that for fields of zero characteristic or for ordered fields (in the latter case inequalities are allowed) these problems can be solved in exponential space and double exponential time. A similar result is obtained for the discretely valued fields. The decision problem for linear sentences with a fixed number of quantifiers can be solved in polynomial time.
Recommendations
- The computational complexity of some problems of linear algebra
- The complexity of almost linear diophantine problems
- The proof complexity of linear algebra
- Linear problems in valued fields
- scientific article; zbMATH DE number 4087025
- Complexity of the satisfiability problem for multilinear forms over a finite field
- The computational complexity of some problems of linear algebra (extended abstract)
- STACS 2005
- An upper bound for the complexity of linearized coverings in a finite field
- scientific article; zbMATH DE number 3983069
Cites work
- A Decision Procedure for the First Order Theory of Real Addition with Order
- Bounds on transfer principles for algebraically closed and complete discretely valued fields
- Complexity of Boolean algebras
- Definability and fast quantifier elimination in algebraically closed fields
- Elimination of quantifiers in algebraic structures
- scientific article; zbMATH DE number 3918343 (Why is no real title available?)
- scientific article; zbMATH DE number 3920550 (Why is no real title available?)
- scientific article; zbMATH DE number 3935016 (Why is no real title available?)
- scientific article; zbMATH DE number 3752829 (Why is no real title available?)
- scientific article; zbMATH DE number 3779296 (Why is no real title available?)
- scientific article; zbMATH DE number 3501006 (Why is no real title available?)
- scientific article; zbMATH DE number 3532959 (Why is no real title available?)
- scientific article; zbMATH DE number 3572309 (Why is no real title available?)
- scientific article; zbMATH DE number 3408928 (Why is no real title available?)
- Presburger arithmetic with bounded quantifier alternation
- The complexity of logical theories
- The complexity of Presburger arithmetic with bounded quantifier alternation depth
- The computational complexity of logical theories
Cited in
(84)- A bibliography of quantifier elimination for real closed fields
- Dines-Fourier-Motzkin quantifier elimination and an application of corresponding transfer principles over ordered fields
- On the parallel complexity of the polynomial ideal membership problem
- Formulation of linear problems and solution by a universal machine
- Automatic derivation of positivity conditions inside boundary elements with the help of the REDLOG computer logic package.
- Linear problems in valued fields
- A survey of some methods for real quantifier elimination, decision, and satisfiability and their applications
- Tropical effective primary and dual Nullstellensätze
- Automatic generation of bounds for polynomial systems with application to the Lorenz system
- Decidable \({\exists}^*{\forall}^*\) first-order fragments of linear rational arithmetic with uninterpreted predicates
- Efficiently and effectively recognizing toricity of steady state varieties
- A logic based approach to finding real singularities of implicit ordinary differential equations
- Algorithmic reduction of biological networks with multiple time scales
- Reachability relations of timed pushdown automata
- A proof of Bel'tyukov-Lipshitz theorem by quasi-quantifier elimination. I: Definitions and GCD-lemma
- On quantified linear implications
- Identifying the parametric occurrence of multiple steady states for some biological networks
- Erratum to: ``Analyzing restricted fragments of the theory of linear arithmetic
- Algorithmic methods for investigating equilibria in epidemic modeling
- Quantifier elimination in automatic loop parallelization
- Multiple object semilinear motion planning
- Some formal tools for analyzing quantum automata.
- A decision procedure for linear ``big O equations
- Convex polarities over ordered fields
- On sets of linear forms of maximal complexity
- Linear Programs and Convex Hulls Over Fields of Puiseux Fractions
- Computing Hopf bifurcations in chemical reaction networks using reaction coordinates
- Polynomial Bell inequalities
- Adapting real quantifier elimination methods for conflict set computation
- Virtual substitution for SMT-solving
- \texttt{SMT-RAT}: an open source \texttt{C++} toolbox for strategic and parallel SMT solving
- Applied Algebraic Geometry in Model Based Design for Manufacturing
- Detection of Hopf bifurcations in chemical reaction networks using convex coordinates
- Parametric Qualitative Analysis of Ordinary Differential Equations: Computer Algebra Methods for Excluding Oscillations (Extended Abstract) (Invited Talk)
- Supporting global numerical optimization of rational functions by generic symbolic convexity tests
- A symbolic-numeric approach to multi-objective optimization in manufacturing design
- Effective Quantifier Elimination for Presburger Arithmetic with Infinity
- An effective implementation of symbolic-numeric cylindrical algebraic decomposition for quantifier elimination
- On the complexity of quantified linear systems
- Classical numerical methods in engineering: a note on existential quantifier elimination under parametric inequality constraints
- An Algebraic Study of Affine Real Ultrafilters
- scientific article; zbMATH DE number 1507955 (Why is no real title available?)
- On the complexity of linear arithmetic with divisibility
- Sur la complexité du principe de Tarski-Seidenberg
- scientific article; zbMATH DE number 1866875 (Why is no real title available?)
- Quantifier elimination for a class of exponential polynomial formulas
- A complexity perspective on entailment of parameterized linear constraints
- scientific article; zbMATH DE number 1405441 (Why is no real title available?)
- Binary reachability of timed pushdown automata via quantifier elimination and cyclic order atoms
- Applying term rewriting methods to finite groups
- Analyzing restricted fragments of the theory of linear arithmetic
- On complexity of the existential and universal theories of finite fields
- An exact correspondence of linear problems and randomizing linear algorithms
- Algorithmic global criteria for excluding oscillations
- Solution formulas for cubic equations without or with constraints
- A Folding Algorithm for Eliminating Existential Variables from Constraint Logic Programs
- Model-theoretic methods in combined constraint satisfiability
- On Hierarchical Reasoning in Combinations of Theories
- Counting and Gröbner bases
- A geometric method for model reduction of biochemical networks with polynomial rate functions
- Sets of Linear Forms Which Are Hard to Compute
- Verification of data-aware process models: checking soundness of Data Petri nets
- Verified Quadratic Virtual Substitution for Real Arithmetic
- Faster one block quantifier elimination for regular polynomial systems of equations
- Positive existential Definability with unit, addition and coprimeness
- Complexity of the satisfiability problem for multilinear forms over a finite field
- A decision algorithm for linear sentences on a PFM
- SMT and functional equation solving over the reals: challenges from the IMO
- The QSMA algorithm for quantifiers in SMT
- Linear quantifier elimination
- A geometric approach to cylindrical algebraic decomposition
- Polynomial-time tractable problems over the p-adic numbers
- Verified Quadratic Virtual Substitution for Real Arithmetic
- Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields
- The complexity of almost linear diophantine problems
- Testing binomiality of chemical reaction networks using comprehensive Gröbner systems
- Better answers to real questions
- Relationships of properties of piecewise affine maps over ordered fields
- Computational complexity of sentences over fields
- Weak quantifier elimination for the full linear theory of the integers
- Solving and visualizing nonlinear parametric constraints in control based on quantifier elimination
- Proof synthesis and reflection for linear arithmetic
- A representation of convex semilinear sets
- Some lower bounds for the complexity of the linear programming feasibility problem over the reals
This page was built for publication: The complexity of linear problems in fields
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1103602)
