A survey on real structural complexity theory
From MaRDI portal
Publication:1280231
zbMath0934.68046MaRDI QIDQ1280231
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
algorithmsundecidabilityJulia setNP-completenessmodel theoryrecursively enumerablehalting problemcomplexity classescontinuous domainreal number modelsanalogs to Turing machineboolean partP versus NPstructure of finite type
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (17)
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
This page was built for publication: A survey on real structural complexity theory
