ECCC-Report TR08-073https://eccc.weizmann.ac.il/report/2008/073Comments and Revisions published for TR08-073en-usThu, 28 Aug 2008 19:35:25 +0300
Paper TR08-073
| Structural complexity of AvgBPP |
Dmitry Itsykson
https://eccc.weizmann.ac.il/report/2008/073We study class AvgBPP that consists of distributional problems that 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 AvgBPP 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 AvgP=AvgBPP. Note that, while it is easy to construct a promise problem that is complete for promise-BPP, it is unknown whether BPP contains complete languages.
We also prove a time hierarchy theorem for AvgBPP (time hierarchy theorem is also unknown for BPP). We compare average-case classes with their classical (worst-case) counterparts and show that the inclusions are proper.
Thu, 28 Aug 2008 19:35:25 +0300https://eccc.weizmann.ac.il/report/2008/073