Computing over the reals with addition and order
From MaRDI portal
Publication:1338216
DOI10.1016/0304-3975(93)00063-BzbMath0822.68028MaRDI QIDQ1338216
Publication date: 9 October 1995
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items
Complexity and dimension, Separation of complexity classes in Koiran's weak model, On the P-NP problem over real matrix rings, On The Complexity of Bounded Time Reachability for Piecewise Affine Systems, On the computational power of dynamical systems and hybrid systems, Generalized Knapsack problems and fixed degree separations, On the complexity of bounded time and precision reachability for piecewise affine systems, P versus NP and computability theoretic constructions in complexity theory over algebraic structures, On NP-completeness for linear machines, Dynamical recognizers: real-time language recognition by analog computers, Generalization of the subset sum problem and cubic forms, Computation over algebraic structures and a classification of undecidable problems, On the computation of Boolean functions by analog circuits of bounded fan-in, An explicit solution to Post's problem over the reals, On Relativizations of the P =? NP Question for Several Structures, Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets, A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF, On a transfer theorem for the \(\text{P}\neq \text{NP}\) conjecture, 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, A hierarchy below the halting problem for additive machines, Exotic quantifiers, complexity classes, and complete problems, Achilles and the tortoise climbing up the hyper-arithmetical hierarchy, Saturation and stability in the theory of computation over the reals, On the computational structure of the connected components of a hard problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Real addition and the polynomial hierarchy
- A note on a \(P \neq NP\) result for a restricted class of real machines
- Analog computation via neural networks
- On digital nondeterminism
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- Bounds for the computational power and learning complexity of analog neural nets
