Generic Complexity of Undecidable Problems

DOI10.1007/978-3-540-74510-5_41MaRDI QIDQ3499790zbMATH OpenOpenAlexFDO

Authors Alexei Myasnikov

Publication date 3 June 2008

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74510-5_41

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Undecidability and degrees of sets of sentences (03D35)

Recommendations

• Generic complexity of undecidable problems
• On the strongly generic undecidability of the halting problem
• Generic undecidability of universal theories
• Generic amplification of recursively enumerable sets
• On the generic undecidability of the halting problem for normalized Turing machines

Cited in

(5)

• On hypercomputation, universal and diagonalization complete problems
• Generic complexity of undecidable problems
• Undecidability in Some Structures Related to Computation Theory
• scientific article; zbMATH DE number 512805 (Why is no real title available?)
• On the strongly generic undecidability of the halting problem

This page was built for publication: Generic Complexity of Undecidable Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3499790)