An average complexity measure that yields tight hierarchies

DOI10.1007/BF01262929zbMath0868.68059MaRDI QIDQ1355380

K. Ruediger Reischuk, Christian Schindelhauer

Publication date: 17 August 1997

Published in: Computational Complexity (Search for Journal in Brave)

zbMATH Keywords

worst case complexityaverage complexity classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability distributions: general theory (60E05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Malign distributions for average case circuit complexity.

Cites Work

• Average case completeness
• On the theory of average case complexity
• Average Case Complete Problems
• The Complexity of Malign Measures
• Unnamed Item

This page was built for publication: An average complexity measure that yields tight hierarchies