How to prove representation-independent independence results

DOI10.1016/0020-0190(87)90191-8zbMath0623.68050OpenAlexW2030070824MaRDI QIDQ1091820

James S. Royer, Stuart A. Kurtz, Michael J. O'Donnell

Publication date: 1987

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90191-8

zbMATH Keywords

input-output behavior of a Turing machinerepresentation-independent independence resultssubrecursive complexity classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Related Items

Index sets and presentations of complexity classes, Gap-languages and log-time complexity classes, A note on da Costa-Doria ``exotic formalizations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Independence results about context-free languages and lower bounds
• Independence results in computer science?
• Unprovability of theorems of complexity theory in weak number theories
• The Expressiveness of Simple and Second-Order Type Structures
• Some independence results for Peano arithmetic