A note on natural complete sets and Goedel numberings

DOI10.1016/0304-3975(82)90132-3zbMath0483.03026OpenAlexW2092992954MaRDI QIDQ1163015

Juris Hartmanis

Publication date: 1982

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(82)90132-3

zbMATH Keywords

complete recursively enumerable setscomputationally simple mappingscomputationally simple reductionsnatural complete setsnatural creative setsnatural Goedel numberings

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25)

Related Items

Reductions among polynomial isomorphism types, On simple and creative sets in NP, On p-creative sets and p-completely creative sets, Composition is almost (but not quite) as good as \(s-1-1\)

Cites Work

• Unnamed Item
• On log-tape isomorphisms of complete sets
• Program size in restricted programming languages
• Optimal enumerations and optimal gödel numberings
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Simple Gödel Numberings, Isomorphisms, and Programming Properties
• On Simple Goedel Numberings and Translations