Counting problems over the reals
From MaRDI portal
Publication:1575534
DOI10.1016/S0304-3975(98)00190-XzbMath0947.68076MaRDI QIDQ1575534
Publication date: 21 August 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (10)
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 ⋮ Semiring reasoning frameworks in AI and their computational complexity ⋮ 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
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Counting problems over the reals
