Concepedia

Complexity Class Separations

Complexity Class Separations is a theoretical construct in computational complexity theory that distinguishes between distinct complexity classes by proving that one class properly contains another, thereby establishing a strict hierarchy in computational resource requirements.

30

Publications

1.1K

Citations

57

Authors

38

Institutions

Publications per year

2017–2026

2

Parents

Publications

30

Separating Nondeterministic Time Complexity Classes

Joel Seiferas, Michael J. Fischer, Albert R. Meyer · Journal of the ACM · 1978 · 180 citations · Full text

, , +8

Algebrization

Scott Aaronson, Avi Wigderson · ACM Transactions on Computation Theory · 2009 · 156 citations

, , +17

The complexity of NISQ

Sitan Chen, Jordan Cotler, Hsin-Yuan Huang et al. · Nature Communications · 2023 · 85 citations · Full text

, , +15

Symposium on Theoretical Aspects of Computer Science

Max Crochemore, Costas S. Iliopoulos, Marcin Kubica et al. · 2008 · 66 citations

, , +14

Algebrization

Scott Aaronson, Avi Wigderson · 2008 · 64 citations

, , +17

1–5 of 30

Authors

57

  1. SA
    Scott Aaronson

    Massachusetts Institute of Technology, United States

    4 publications · 261 citations

    4

    h-index

  2. LT
    Leen Torenvliet

    University of Amsterdam, Netherlands

    3 publications · 75 citations

    3

    h-index

  3. JS
    Joel Seiferas

    University of Rochester, United States

    3 publications · 234 citations

    3

    h-index

  4. AW
    Avi Wigderson

    Hebrew University of Jerusalem, Israel

    3 publications · 237 citations

    3

    h-index

  5. HB
    Harry Buhrman

    Centrum Wiskunde & Informatica, Netherlands

    3 publications · 75 citations

    3

    h-index

1–5 of 57

Institutions

38

  1. University of California, Berkeley

    Berkeley, United States

    3 h-index

    4 publications

    229 citations

  2. University of Rochester

    Rochester, United States

    3 h-index

    3 publications

    58 citations

  3. Institute for Advanced Study

    Princeton, United States

    2 h-index

    2 publications

    84 citations

  4. Microsoft (United States)

    Redmond, United States

    2 h-index

    2 publications

    99 citations

  5. Massachusetts Institute of Technology

    Cambridge, United States

    2 h-index

    2 publications

    244 citations

  6. University of Washington

    Seattle, United States

    2 h-index

    2 publications

    196 citations

  7. Moscow Institute of Thermal Technology

    Moscow, Russia

    2 h-index

    2 publications

    173 citations

  8. Universitat Pompeu Fabra

    Barcelona, Spain

    2 h-index

    2 publications

    70 citations

1–8 of 38

Venues

  1. SIAM Journal on Computing

    3 publications · 64 citations

    3

    h-index

  2. Journal of the ACM

    JACM · 2 publications · 196 citations

    2

    h-index

  3. Theoretical Computer Science

    2 publications · 50 citations

    2

    h-index

  4. ArXiv.org

    Repository · 2 publications · 30 citations

    2

    h-index

  5. Information and Computation

    2 publications · 60 citations

    2

    h-index

1–5