Structure in average case complexity

DOI10.1007/BFB0015409MaRDI QIDQ6487946zbMATH OpenFDO

Authors Christoph Karg, Rainer Schuler

Publication date 21 March 2023

Full work available at URL https://doi.org/10.1007/BFB0015409

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Structural average case complexity
• scientific article; zbMATH DE number 512870
• On the theory of average case complexity
• Fine Separation of Average-Time Complexity Classes
• Structural Complexity of AvgBPP

Cites work

• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 512799 (Why is no real title available?)
• A hierarchy for nondeterministic time complexity
• Average Case Complete Problems
• Average case completeness
• Computational complexity of real functions
• On average time hierarchies
• On the theory of average case complexity
• Some properties of sets tractable under every polynomial-time computable distribution
• Two-Tape Simulation of Multitape Turing Machines

Cited in

(4)

• Average-Case Completeness in Tag Systems
• Using depth to capture average-case complexity.
• scientific article; zbMATH DE number 5081744 (Why is no real title available?)
• Average-Case Complexity

This page was built for publication: Structure in average case complexity

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