Concepedia

Bpp Complexity Class

The BPP Complexity Class is a complexity class consisting of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded away from 1/3 for all instances.

43

Publications

4.2K

Citations

73

Authors

46

Institutions

Publications per year

2017–2026

3

Parents

Publications

43

PP is as Hard as the Polynomial-Time Hierarchy

Seinosuke Toda · SIAM Journal on Computing · 1991 · 677 citations

, , +17

<i>P = BPP</i> if <i>E</i> requires exponential circuits

Russell Impagliazzo, Avi Wigderson · 1997 · 544 citations

, , +6

Relative to a Random Oracle<i>A</i>, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1

Charles H. Bennett, John Gill · SIAM Journal on Computing · 1981 · 379 citations

, , +12

Quantum computing, postselection, and probabilistic polynomial-time

Scott Aaronson · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · 2005 · 319 citations

, , +16

Complexity classes in communication complexity theory

László Babai, Péter Frankl, Janoš Šimon · 1986 · 318 citations · Full text

, , +15

1–5 of 43

Authors

73

  1. RI
    Russell Impagliazzo

    University of California San Diego, United States

    7 publications · 976 citations

    7

    h-index

  2. AW
    Avi Wigderson

    Hebrew University of Jerusalem, Israel

    6 publications · 1.1K citations

    6

    h-index

  3. LF
    Lance Fortnow

    University of Chicago, United States

    3 publications · 99 citations

    3

    h-index

  4. DP
    David P. DiVincenzo

    IBM Research - Thomas J. Watson Research Center, United States

    3 publications · 240 citations

    3

    h-index

  5. BM
    Barbara M. Terhal

    IBM (United States), United States

    3 publications · 240 citations

    3

    h-index

1–5 of 73

Institutions

46

  1. Hebrew University of Jerusalem

    Jerusalem, Israel

    7 h-index

    8 publications

    1K citations

  2. University of California San Diego

    San Diego, United States

    7 h-index

    8 publications

    1.2K citations

  3. University of Chicago

    Chicago, United States

    3 h-index

    6 publications

    802 citations

  4. Massachusetts Institute of Technology

    Cambridge, United States

    2 h-index

    3 publications

    81 citations

  5. Universität Ulm

    Ulm, Germany

    2 h-index

    2 publications

    114 citations

  6. IBM (United States)

    Armonk, United States

    2 h-index

    8 publications

    900 citations

  7. Institute for Advanced Study

    Princeton, United States

    2 h-index

    3 publications

    238 citations

  8. University of Toronto

    Toronto, Canada

    2 h-index

    4 publications

    54 citations

1–8 of 46

Venues

  1. SIAM Journal on Computing

    7 publications · 1.2K citations

    7

    h-index

  2. Electronic Notes in Theoretical Computer Science

    ENTCS · 2 publications · 34 citations

    2

    h-index

  3. Information Processing Letters

    2 publications · 269 citations

    2

    h-index

  4. Physical Review Letters

    PRL · 1 publications · 91 citations

    1

    h-index

  5. arXiv (Cornell University)

    Repository · 1 publications · 15 citations

    1

    h-index

1–5