Structural average case complexity

DOI10.1006/JCSS.1996.0024MaRDI QIDQ1916530zbMATH OpenOpenAlexFDO

Authors Rainer Schuler, Tomoyuki Yamakami

Publication date 27 January 1997

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/01da7e4e2efbfe77e8587a7f47bb8dbed63b4e23

zbMATH Keywords

average-case complexity measurepolynomial on average

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the theory of average case complexity
• scientific article; zbMATH DE number 512799
• scientific article; zbMATH DE number 512870

Cited in

(20)

• Average case complexity under the universal distribution equals worst- case complexity
• Reductions do not preserve fast convergence rates in average time
• Polynomial time samplable distributions
• Encoding invariance in average case complexity
• Average-case bit-complexity theory of real functions
• Notes on Levin's theory of average-case complexity
• Randomizing Reductions of Search Problems
• Structural Complexity of AvgBPP
• scientific article; zbMATH DE number 5081744 (Why is no real title available?)
• Average-Case Complexity
• scientific article; zbMATH DE number 1332675 (Why is no real title available?)
• scientific article; zbMATH DE number 512799 (Why is no real title available?)
• scientific article; zbMATH DE number 512870 (Why is no real title available?)
• Worst-Case to Average-Case Reductions for Subclasses of P
• Using depth to capture average-case complexity.
• Average-case intractability vs. worst-case intractability
• Sets computable in polynomial time on average
• Reductions and convergence rates of average time
• Structural complexity of AvgBPP
• Structure in average case complexity

This page was built for publication: Structural average case complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1916530)