文章基本信息

标题：Average-Case Intractability vs. Worst-Case Intractability
本地全文：下载
作者：Johannes Köbler ; Rainer Schuler
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We use the assumption that all sets in NP (or other levels of the polynomial-time hierarchy) have efficient average-case algorithms to derive collapse consequences for MA, AM, and various subclasses of P/poly. As a further consequence we show for C in {P(PP), PSPACE} that C is not tractable in the average-case unless C is equal to P.
关键词：average-case complexity, P/poly, Probabilistic Complexity Classes