Upward separations and weaker hypotheses in resource-bounded measure

DOI10.1016/J.TCS.2007.08.012MaRDI QIDQ2465636zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

resource-bounded measuredouble-exponential timeNP-machine hypothesis

Mathematics Subject Classification ID

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

Recommendations

• An upward measure separation theorem
• Results on resource-bounded measure
• Relative to a random oracle, NP is not small
• Resource-bounded measure on probabilistic classes
• scientific article; zbMATH DE number 1346358

Cites work

• scientific article; zbMATH DE number 1261804 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1072536 (Why is no real title available?)
• Almost every set in exponential time is P-bi-immune
• Almost everywhere high nonuniform complexity
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• Dimension, entropy rates, and compression
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Hardness vs randomness
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Limitations of the upward separation technique
• Measure, Stochasticity, and the Density of Hard Languages
• Resource bounded randomness and weakly complete problems
• Separation of NP-completeness notions
• Tally languages and complexity classes
• The Complexity of Decision Versus Search
• The zero-one law holds for BPP
• Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)

Cited in

(2)

• An upward measure separation theorem
• Lines missing every random point

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)