Independence results about context-free languages and lower bounds
From MaRDI portal
Publication:1071500
DOI10.1016/0020-0190(85)90026-2zbMath0586.68029MaRDI QIDQ1071500
Publication date: 1985
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/6446
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
68Q65: Abstract data types; algebraic specification
Related Items
If not empty, NP-P is topologically large, How to prove representation-independent independence results, Gap-languages and log-time complexity classes
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item