Abstract

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.