A survey on real structural complexity theory

zbMath0934.68046MaRDI QIDQ1280231

Christian Michaux, Klaus Meer

Publication date: 14 March 1999

Published in: Bulletin of the Belgian Mathematical Society - Simon Stevin (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/120198

zbMATH Keywords

algorithmsundecidabilityJulia setNP-completenessmodel theoryrecursively enumerablehalting problemcomplexity classescontinuous domainreal number modelsanalogs to Turing machineboolean partP versus NPstructure of finite type

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursively (computably) enumerable sets and degrees (03D25)

Related Items

On the computational power of dynamical systems and hybrid systems, On the expressiveness and decidability of o-minimal hybrid systems, \(\mathbf P =\mathbf{NP}\) for some structures over the binary words, Two situations with unit-cost: ordered abelian semi-groups and some commutative rings, Elimination of constants from machines over algebraically closed fields, On NP-completeness for linear machines, Average-Price and Reachability-Price Games on Hybrid Automata with Strong Resets, An explicit solution to Post's problem over the reals, Kolmogorov Complexity Theory over the Reals, A survey of recursive analysis and Moore's notion of real computation, Achilles and the tortoise climbing up the hyper-arithmetical hierarchy, Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics, Counting problems over the reals, Isomorphism theorem for BSS recursively enumerable sets over real closed fields, Some aspects of studying an optimization or decision problem in different computational models, On the computational structure of the connected components of a hard problem, Logics which capture complexity classes over the reals