A note on measuring in P

DOI10.1016/j.tcs.2004.01.037zbMath1068.68065OpenAlexW2030743944MaRDI QIDQ596092

Olivier Powell

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

zbMATH Keywords

MartingaleComputational complexityResource-bounded measure

Mathematics Subject Classification ID

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