Results on resource-bounded measure

DOI10.1007/3-540-63165-8_176zbMath1401.68087OpenAlexW2124329210MaRDI QIDQ4571951

Harry Buhrman, Stephen A. Fenner, Lance J. Fortnow

Publication date: 4 July 2018

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://ir.cwi.nl/pub/1931

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

Hard Instances of Algorithms and Proof Systems ⋮ The zero-one law holds for BPP

Cites Work

• Unnamed Item
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• Almost everywhere high nonuniform complexity
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• Almost every set in exponential time is P-bi-immune
• STACS 95. 12th annual symposium on theoretical aspects of computer science, Munich, Germany, March 2--4, 1995. Proceedings
• Proving properties of interactive proofs by a generalized counting technique
• Category and Measure in Complexity Classes
• On the cutting edge of relativization: The resource bounded injury method

This page was built for publication: Results on resource-bounded measure