Complexity lower bounds for computation trees with elementary transcendental function gates
From MaRDI portal
Publication:1365876
DOI10.1016/0304-3975(95)00159-XzbMath0877.68086WikidataQ30048515 ScholiaQ30048515MaRDI QIDQ1365876
Nikolaj N. jun. Vorob'ev, Dima Yu. Grigoriev
Publication date: 9 September 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items (8)
On the Vapnik-Chervonenkis dimension of computer programs which use transcendental elementary operations ⋮ Complexity lower bounds for computation trees with elementary transcendental function gates ⋮ Rough analysis of computation trees ⋮ Randomization and the computational power of analytic and algebraic decision trees ⋮ Complexity of gene circuits, Pfaffian functions and the morphogenesis problem. ⋮ Lower bound on testing membership to a polyhedron by algebraic decision and computation trees ⋮ Algorithms and complexity in biological pattern formation problems ⋮ Instability, complexity, and evolution
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Solving systems of polynomial inequalities in subexponential time
- Semianalytic and subanalytic sets
- On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
- The complexity of deciding consistency of systems of polynomials in exponent inequalities
- Complexity of deciding Tarski algebra
- Finding irreducible components of some real transcendental varieties
- Complexity lower bounds for computation trees with elementary transcendental function gates
- Complexity of stratifications of semi-Pfaffian sets
- Complements of subanalytic sets and existential formulas for analytic functions
- Lower bounds on testing membership to a polyhedron by algebraic decision trees
- Real-Analytic Desingularization and Subanalytic Sets: An Elementary Approach
- On the Polyhedral Decision Problem
- Topological Properties of Subanalytic Sets
- Sur la complexité du principe de Tarski-Seidenberg
- On Computing Algebraic Functions Using Logarithms and Exponentials
- On the Betti Numbers of Real Varieties
- Decision tree complexity and Betti numbers
This page was built for publication: Complexity lower bounds for computation trees with elementary transcendental function gates
