If not empty, NP-P is topologically large
From MaRDI portal
Publication:688157
DOI10.1016/0304-3975(93)90161-LzbMath0781.68072MaRDI QIDQ688157
Publication date: 17 February 1994
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(93)90161-l
68Q25: Analysis of algorithms and problem complexity
Related Items
Effective category and measure in abstract complexity theory, On the topological size of p-m-complete degrees, Effective category and measure in abstract complexity theory
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on a theorem by Ladner
- A low and a high hierarchy within NP
- Independence results about context-free languages and lower bounds
- Theories of computational complexity
- Complexity of Presburger arithmetic with fixed quantifier dimension
- Immunity, Relativizations, and Nondeterminism
- Category and Measure in Complexity Classes
- Simplicity, Relativizations and Nondeterminism
- Bi-immune sets for complexity classes
- Alternation
- Topological Size of Sets of Partial Recursive Functions
- On the Structure of Polynomial Time Reducibility
- P-Printable Sets