کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4662073 | 1633501 | 2010 | 11 صفحه PDF | دانلود رایگان |
We study the class that consists of distributional problems which can be solved in average polynomial time (in terms of Levin’s average-case complexity) by randomized algorithms with bounded error. We prove that there exists a distributional problem that is complete for under polynomial time samplable distributions. Since we use deterministic reductions, the existence of a deterministic algorithm with average polynomial running time for our problem would imply . Note that, while it is easy to construct a promise problem that is complete for , it is unknown whether contains complete languages. We also prove a time hierarchy theorem for (there are no known time hierarchy theorems for ). We compare average-case classes with their classical (worst-case) counterparts and show that the inclusions are proper.
Journal: Annals of Pure and Applied Logic - Volume 162, Issue 3, December 2010, Pages 213-223