Towards the Actual Relationship Between NP and Exponential Time
From MaRDI portal
Publication:4238424
DOI10.1002/malq.19990450104zbMath0933.03046OpenAlexW2004234313MaRDI QIDQ4238424
Publication date: 20 March 2000
Published in: Mathematical Logic Quarterly (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/malq.19990450104
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
- Oracle-dependent properties of the lattice of NP sets
- The complexity of facets (and some facets of complexity)
- On sparse sets in NP-P
- The random oracle hypothesis is false
- On the random oracle hypothesis
- Relativizations comparing NP and exponential time
- Sparse Sets in : Relativizations
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- A note on balanced immunity
- Separating Nondeterministic Time Complexity Classes
- Two-Tape Simulation of Multitape Turing Machines
- On Languages Accepted in Polynomial Time
- The complexity of theorem-proving procedures
This page was built for publication: Towards the Actual Relationship Between NP and Exponential Time