Upward separations and weaker hypotheses in resource-bounded measure
From MaRDI portal
Publication:2465636
DOI10.1016/J.TCS.2007.08.012zbMATH Open1147.68526OpenAlexW2014604045MaRDI QIDQ2465636FDOQ2465636
Authors: Ryan C. Harkins, John M. Hitchcock 
Publication date: 7 January 2008
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2007.08.012
Recommendations
Cites Work
- Title not available (Why is that?)
- Hardness vs randomness
- Almost everywhere high nonuniform complexity
- Measure, Stochasticity, and the Density of Hard Languages
- Cook versus Karp-Levin: Separating completeness notions if NP is not small
- Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Resource bounded randomness and weakly complete problems
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Separation of NP-completeness notions
- Tally languages and complexity classes
- The Complexity of Decision Versus Search
- Almost every set in exponential time is P-bi-immune
- The zero-one law holds for BPP
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- Dimension, entropy rates, and compression
- Limitations of the upward separation technique
Cited In (2)
This page was built for publication: Upward separations and weaker hypotheses in resource-bounded measure
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2465636)
