Counting problems over the reals

DOI10.1016/S0304-3975(98)00190-XzbMath0947.68076MaRDI QIDQ1575534

Klaus Meer

Publication date: 21 August 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

model theorycounting problemreal number model\(\mathbb R\)-structures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem, A complex analogue of Toda's theorem, On the algebraic complexity of some families of coloured Tutte polynomials, A numerical algorithm for zero counting. I: Complexity and accuracy, Kolmogorov Complexity Theory over the Reals, Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets, Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals, Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals, From a zoo to a zoology: Towards a general theory of graph polynomials

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Universal resolution for NP-complete problems
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• Optimization, approximation, and complexity classes
• A survey on real structural complexity theory
• Descriptive complexity of \(\#\)P functions
• Complexity of Bezout's Theorem I: Geometric Aspects
• Logics which capture complexity classes over the reals
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines