The complexity of elementary algebra and geometry

From MaRDI portal
Revision as of 01:28, 31 January 2024 by Import240129110113 (talk | contribs) (Created automatically from import240129110113)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Publication:1096620

DOI10.1016/0022-0000(86)90029-2zbMath0634.03031OpenAlexW2006918089MaRDI QIDQ1096620

Michael Ben-Or, John H. Reif, Dexter Kozen

Publication date: 1986

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(86)90029-2




Related Items (58)

A polynomial solution for the Potato-peeling problemReasoning about probabilistic sequential programsRational Points and Trace Forms on a Finite Algebra over a Real Closed FieldOn the complexity of some basic problems in computational convexity. I. Containment problemsOn maps which preserve semipositivity and quantifier elimination theory for real numbersA bibliography of quantifier elimination for real closed fieldsPolar varieties, real equation solving, and data structures: the hypersurface caseOn computing a set of points meeting every cell defined by a family of polynomials on a varietyReal quantifier elimination is doubly exponentialA polynomial-time algorithm for the topological type of real algebraic curveParallel computational geometryAlgebraic decomposition of regular curvesNote on the computational complexity of \(j\)-radii of polytopes in \(\mathbb R^ n\)Finitely representable databasesOn the complexity of \(p\)-adic basic semi-algebraic setsParametric Markov chains: PCTL complexity and fraction-free Gaussian eliminationBisimilarity of DiagramsQueries with arithmetical constraintsReachability and connectivity queries in constraint databasesBetween the Rings $${\mathbb Z}/p^n{\mathbb Z}$$ and the Ring $${\mathbb Z}_p$$: Issues of Axiomatizability, Definability and DecidabilityLinear constraint query languages expressive power and complexityCondition number based complexity estimate for solving polynomial systemsClassifying the computational complexity of problemsLinear solving for sign determinationTarski’s Influence on Computer ScienceUnnamed ItemA uniform method for proving lower bounds on the computational complexity of logical theoriesExistence and uniqueness of the real closure of an ordered field without Zorn's lemmaOn 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 realsOn the computational complexity and geometry of the first-order theory of the reals. III: Quantifier eliminationOn information invariants in roboticsThe complexity of deciding consistency of systems of polynomials in exponent inequalitiesMetric estimates and membership complexity for Archimedean amoebae and tropical hypersurfacesComputational complexity of determining which statements about causality hold in different space-time modelsDetecting cusps and inflection points in curvesDeciding consistency of systems of exponential-polynomial inequalities in subexponential timeNC algorithms for real algebraic numbersElementary recursive quantifier elimination based on Thom encoding and sign determinationCounting connected components of a semialgebraic set in subexponential timeA parametric representation of totally mixed Nash equilibriaComplexity of deciding the first-order theory of real closed fieldsThom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic setsAlgebraic optimization: The Fermat-Weber location problemThe uniform measure of simple regular sets of infinite treesSolving degenerate sparse polynomial systems fasterComputing AmoebasSur la complexité du principe de Tarski-SeidenbergA logic for reasoning about probabilitiesComplexity of computation on real algebraic numbersGeneric computation of the real closure of an ordered field.Dynamic evaluation and real closure.A ModalWalk Through SpaceQuerying spatial databases via topological invariantsUnnamed ItemReal addition and the polynomial hierarchyParallel algorithms for matrix normal formsSolving systems of polynomial inequalities over a real closed field in subexponential timeComputation of equilibria in noncooperative games




Cites Work




This page was built for publication: The complexity of elementary algebra and geometry