Standard

Structural complexity of AvgBPP. / Itsykson, Dmitry.

In: Annals of Pure and Applied Logic, Vol. 162, No. 3, 01.12.2010, p. 213-223.

Research output: Contribution to journal › Article › peer-review

Harvard

Itsykson, D 2010, 'Structural complexity of AvgBPP', Annals of Pure and Applied Logic, vol. 162, no. 3, pp. 213-223. https://doi.org/10.1016/j.apal.2010.09.006

APA

Itsykson, D. (2010). Structural complexity of AvgBPP. Annals of Pure and Applied Logic, 162(3), 213-223. https://doi.org/10.1016/j.apal.2010.09.006

Vancouver

Itsykson D. Structural complexity of AvgBPP. Annals of Pure and Applied Logic. 2010 Dec 1;162(3):213-223. https://doi.org/10.1016/j.apal.2010.09.006

Author

Itsykson, Dmitry. / Structural complexity of AvgBPP. In: Annals of Pure and Applied Logic. 2010 ; Vol. 162, No. 3. pp. 213-223.

BibTeX

@article{46724b32d32544ddae800f5e4f5ac69f,
title = "Structural complexity of AvgBPP",
abstract = "We study the class AvgBPP 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 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 (there are no known time hierarchy theorems for BPP). We compare average-case classes with their classical (worst-case) counterparts and show that the inclusions are proper.",
keywords = "Average-case complexity, BPP, Complete problems, Errorless heuristics, Randomized algorithms, Time hierarchy",
author = "Dmitry Itsykson",
year = "2010",
month = dec,
day = "1",
doi = "10.1016/j.apal.2010.09.006",
language = "English",
volume = "162",
pages = "213--223",
journal = "Annals of Pure and Applied Logic",
issn = "0168-0072",
publisher = "Elsevier",
number = "3",

}

RIS

TY - JOUR

T1 - Structural complexity of AvgBPP

AU - Itsykson, Dmitry

PY - 2010/12/1

Y1 - 2010/12/1

N2 - We study the class AvgBPP 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 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 (there are no known time hierarchy theorems for BPP). We compare average-case classes with their classical (worst-case) counterparts and show that the inclusions are proper.

AB - We study the class AvgBPP 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 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 (there are no known time hierarchy theorems for BPP). We compare average-case classes with their classical (worst-case) counterparts and show that the inclusions are proper.

KW - Average-case complexity

KW - BPP

KW - Complete problems

KW - Errorless heuristics

KW - Randomized algorithms

KW - Time hierarchy

UR - http://www.scopus.com/inward/record.url?scp=78649475202&partnerID=8YFLogxK

U2 - 10.1016/j.apal.2010.09.006

DO - 10.1016/j.apal.2010.09.006

M3 - Article

AN - SCOPUS:78649475202

VL - 162

SP - 213

EP - 223

JO - Annals of Pure and Applied Logic

JF - Annals of Pure and Applied Logic

SN - 0168-0072

IS - 3

ER -

ID: 49786895