On sparse oracles separating feasible complexity classes
From MaRDI portal
DOI10.1016/0020-0190(88)90176-7zbMATH Open0658.68055OpenAlexW2088269446MaRDI QIDQ1111385FDOQ1111385
Authors: J. Hartmanis, Lane A. Hemaspaandra 
Publication date: 1988
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/6547
Recommendations
Kolmogorov complexitypolynomial-time hierarchysparse oracleclasses of languagesP-printabilityrelativationseparating NP from P in worlds where \(P=NP\)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Quantitative Relativizations of Complexity Classes
- Complexity and structure
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Computation times of NP sets of different densities
- Positive Relativizations of Complexity Classes
- Continuous optimization problems and a polynomial hierarchy of real functions
- Title not available (Why is that?)
Cited In (13)
- Robust machines accept easy sets
- Separating complexity classes with tally oracles
- Sparse Sets in : Relativizations
- Structural properties of oracle classes
- Title not available (Why is that?)
- The strong exponential hierarchy collapses
- Title not available (Why is that?)
- Title not available (Why is that?)
- Complexity classes and sparse oracles
- On sets polynomially enumerable by iteration
- On the complexity of ranking
- Separability and one-way functions
- Title not available (Why is that?)
This page was built for publication: On sparse oracles separating feasible complexity classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1111385)
