An explicit solution to Post's problem over the reals
From MaRDI portal
Publication:2479313
DOI10.1016/J.JCO.2006.09.004zbMATH Open1151.03019OpenAlexW1590722750MaRDI QIDQ2479313FDOQ2479313
Authors: Klaus Meer, Martin Ziegler 
Publication date: 26 March 2008
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jco.2006.09.004
Recommendations
- Fundamentals of Computation Theory
- scientific article; zbMATH DE number 65647
- Publication:4729772
- Two \(P\)-complete problems in the theory of the reals
- scientific article; zbMATH DE number 176763
- On the solvability of the positive real lemma equations.
- A completion problem over the field of real numbers
- A continuous, constructive solution to Hilbert's \(17^{th}\) problem
- On the constructive Dedekind reals
- A Wronskian approach to the real \(\tau\)-conjecture
Other Turing degree structures (03D28) Turing machines and related notions (03D10) Undecidability and degrees of sets of sentences (03D35)
Cites Work
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- Title not available (Why is that?)
- On the Structure of Polynomial Time Reducibility
- Algorithms in real algebraic geometry
- Title not available (Why is that?)
- Title not available (Why is that?)
- Computing over the reals with addition and order
- Computing over the reals with addition and order: Higher complexity classes
- Completeness and reduction in algebraic complexity theory
- Recursively enumerable sets of positive integers and their decision problems
- Title not available (Why is that?)
- Saturation and stability in the theory of computation over the reals
- A note on non-complete problems in \(NP_\mathbb{R}\)
- On the Structure of $\cal NP_\Bbb C$
- TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
- Title not available (Why is that?)
- On the Linear Independence of Fractional Powers of Integers
- Title not available (Why is that?)
- Post's problem for supertasks has both positive and negative solutions
- The Arithmetical Hierarchy Over the Reals
- A uniform approach to obtain diagonal sets in complexity classes
- Classical physics and the Church--Turing Thesis
- Real number models under various sets of operations
- A survey on real structural complexity theory
- Irreducible polynomials with integral coefficients have succinct certificates
- Hypercomputation with quantum adiabatic processes
- Existence and Uniqueness of Interpolating Rational Functions
- Computability Over Arbitrary Fields
Cited In (13)
- Some initial thoughts on bounded query computations over the reals
- Logical Approaches to Computational Barriers
- Computation over algebraic structures and a classification of undecidable problems
- 2010 North American Annual Meeting of the Association for Symbolic Logic
- Discussion on “An effective method for the explicit solution of sequential problems on the real line” by Sören Christensen
- Real computational universality: the word problem for a class of groups with infinite presentation
- A hierarchy below the halting problem for additive machines
- A topological view on algebraic computation models
- The cardinality of an oracle in Blum-Shub-Smale computation
- Computational processes, observers and Turing incompleteness
- Generalized finite automata over real and complex numbers
- Post's problem for supertasks has both positive and negative solutions
- Fundamentals of Computation Theory
This page was built for publication: An explicit solution to Post's problem over the reals
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2479313)
