On the theory of average case complexity
On the theory of average case complexity
复制标题
平均情况复杂度理论
DOI：
10.1145/73007.73027
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
M. Luby
中科院分区：
文献类型：
--
作者：
S. Ben;B. Chor;Oded Goldreich;M. Luby
仅给出摘要形式，如下所示。作者进一步发展了L.A.莱文以前的工作主要集中在完全问题的存在。本作者扩大范围的计算复杂性的其他基本问题。他们的成果包括：（1）在平均情况复杂度的背景下搜索和决策问题的等价性;（2）在保持平均多项式时间的约简下对分布NP的结构的初步分析;（3）证明如果所有分布NP都在平均多项式时间内，则非确定性指数时间等于确定性指数时间（即，在最坏情况下的层次结构中的崩溃）;以及（4）关于其他复杂性类（如平均对数空间）的定义和基本定理。<<ETX>>
Summary form only given, as follows. The authors take the next step in developing the theory of average case complexity initiated by L.A. Levin. Previous work has focused on the existence of complete problems. The present authors widen the scope to other basic questions in computational complexity. Their results include: (1) the equivalence of search and decision problems in the context of average case complexity; (2) an initial analysis of the structure of distributional-NP under reductions which preserve average polynomial-time; (3) a proof that if all distributional-NP is in average polynomial-time then nondeterministic exponential-time equals deterministic exponential time (i.e. a collapse in the worst-case hierarchy); and (4) definitions and basic theorems regarding other complexity classes such as average log space.<<ETX>>