Independence results about context-free languages and lower bounds

DOI10.1016/0020-0190(85)90026-2zbMath0586.68029OpenAlexW2085310804MaRDI QIDQ1071500

Juris Hartmanis

Publication date: 1985

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

Full work available at URL: https://hdl.handle.net/1813/6446

zbMATH Keywords

provabilityrecursive oracles

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Abstract data types; algebraic specification (68Q65)

Related Items (5)

How to prove representation-independent independence results ⋮ Gap-languages and log-time complexity classes ⋮ Incompleteness Theorems, Large Cardinals, and Automata Over Finite Words ⋮ Incompleteness Theorems, Large Cardinals, and Automata over Finite Words ⋮ If not empty, NP-P is topologically large

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the structure of sets in NP and other complexity classes
• A uniform approach to obtain diagonal sets in complexity classes
• Arithmetical hierarchy and complexity of computation
• On the Structure of Polynomial Time Reducibility
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• On Isomorphisms and Density of $NP$ and Other Complete Sets

This page was built for publication: Independence results about context-free languages and lower bounds