Towards the Actual Relationship Between NP and Exponential Time

DOI10.1002/malq.19990450104zbMath0933.03046OpenAlexW2004234313MaRDI QIDQ4238424

Gerhard Lischke

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

zbMATH Keywords

complexity classesrandom oracleexponential timeNPsparse setimmune setoracle construction

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Immunity and pseudorandomness of context-free languages

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