Annals of Pure and Applied Logic 162 (3):213-223 (2010)

We study the class that consists of distributional problems which can be solved in average polynomial time 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. We compare average-case classes with their classical counterparts and show that the inclusions are proper.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2010.09.006
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 51,639
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Computation Models for Parameterized Complexity.Marco Cesati & Miriam Dilanni - 1997 - Mathematical Logic Quarterly 43 (2):179-202.
Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.
On Nondeterminism, Enumeration Reducibility and Polynomial Bounds.Kate Copestake - 1997 - Mathematical Logic Quarterly 43 (3):287-310.
On the Complexity of the Pancake Problem.Fuxiang Yu - 2007 - Mathematical Logic Quarterly 53 (4):532-546.
Multifunction Algebras and the Provability of PH↓.Chris Pollett - 2000 - Annals of Pure and Applied Logic 104 (1-3):279-303.
A Step Towards a Complexity Theory for Analog Systems.K. Meer & M. Gori - 2002 - Mathematical Logic Quarterly 48 (S1):45-58.
Polynomial Time Uniform Word Problems.Stanley Burris - 1995 - Mathematical Logic Quarterly 41 (2):173-182.
The Analytic Polynomial-Time Hierarchy.Herbert Baier & Klaus W. Wagner - 1998 - Mathematical Logic Quarterly 44 (4):529-544.
Le Probleme des Grandes Puissances et Celui des Grandes Racines.Natacha Portier - 2000 - Journal of Symbolic Logic 65 (4):1675-1685.
On the Complexity of Alpha Conversion.Rick Statman - 2007 - Journal of Symbolic Logic 72 (4):1197 - 1203.


Added to PP index

Total views
12 ( #720,065 of 2,331,237 )

Recent downloads (6 months)
1 ( #589,741 of 2,331,237 )

How can I increase my downloads?


My notes