Average case completeness
作者：
Highlights：
•
摘要
We explain and advance Levin's theory of average case completeness. In particular, we exhibit examples of problems complete in the average case and prove a limitation on the power of deterministic reductions.
论文关键词：
论文评审过程：Received 28 April 1988, Revised 3 October 1989, Available online 2 December 2003.
论文官网地址：https://doi.org/10.1016/0022-0000(91)90007-R
