Average case completeness
Gurevich, Yuri
1991-06
Citation: Gurevich, Yuri (1991/06)."Average case completeness." Journal of Computer and System Sciences 42(3): 346-398. <http://hdl.handle.net/2027.42/29307>
Abstract: 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.
DOIs: http://dx.doi.org/10.1016/0022-0000(91)90007-R
URI: http://www.sciencedirect.com/science/article/B6WJ0-4B4RJ4G-1C/2/4afa965055e4950b5e3e1ef99df4a402
Handle: http://hdl.handle.net/2027.42/29307
Show full item record

PDF file
Download
Name: 0000370.pdf
Size: 3MB
Format: PDF

This item appears in the following Collection(s)


Search Deep Blue

Advanced Search

Browse by

My Account

Information


MLibrary logo