A note on measuring in P
From MaRDI portal
Publication:596092
DOI10.1016/j.tcs.2004.01.037zbMath1068.68065OpenAlexW2030743944MaRDI QIDQ596092
Publication date: 10 August 2004
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2004.01.037
Real- or complex-valued set functions (28A10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Unnamed Item
- Unnamed Item
- Cook versus Karp-Levin: Separating completeness notions if NP is not small
- Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
- Almost everywhere high nonuniform complexity
- Almost every set in exponential time is P-bi-immune
- Measure on \(P\): Strength of the notion
- Resource bounded randomness and weakly complete problems
- Almost complete sets.
- Weakly complete problems are not rare
- Measure on P: Robustness of the notion
- Measure, Stochasticity, and the Density of Hard Languages
- Observations on measure and lowness for Δ 2 P
- The Complexity and Distribution of Hard Problems
- Weakly Hard Problems