Complete distributional problems, hard languages, and resource-bounded measure
From MaRDI portal
Publication:1575682
DOI10.1016/S0304-3975(99)00295-9zbMath0947.68085OpenAlexW2049843410MaRDI QIDQ1575682
Publication date: 21 August 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(99)00295-9
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Cook versus Karp-Levin: Separating completeness notions if NP is not small
- A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
- Average case completeness
- On the theory of average case complexity
- Almost everywhere high nonuniform complexity
- Reductions do not preserve fast convergence rates in average time
- Computation times of NP sets of different densities
- Almost every set in exponential time is P-bi-immune
- On the NP-isomorphism problem with respect to random instances
- On the definitions of some complexity classes of real numbers
- Bi-immune sets for complexity classes
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- Average Case Complete Problems
- Fine Separation of Average-Time Complexity Classes
- Matrix Transformation Is Complete for the Average Case
- P-Printable Sets
- On the Computational Complexity of Algorithms
This page was built for publication: Complete distributional problems, hard languages, and resource-bounded measure
