Concepedia

Polynomial Hierarchy

The Polynomial Hierarchy is a hierarchy of complexity classes that extends the classes P, NP, and co-NP by iterative oracle access to decision problems, where each level consists of problems solvable in polynomial time with a logarithmic number of alternations between existential and universal quantifiers over polynomially bounded nondeterministic computations.

284

Publications

17.3K

Citations

381

Authors

229

Institutions

Publications per year

2017–2026

45

Parents

Publications

284

Algebraic methods for interactive proof systems

Carsten Lund, Lance Fortnow, Howard Karloff et al. · Journal of the ACM · 1992 · 702 citations · Full text

, , +17

PP is as Hard as the Polynomial-Time Hierarchy

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

, , +17

Separating the polynomial-time hierarchy by oracles

Andrew Chi-Chih Yao · 1985 · 554 citations

, , +17

Disjunctive datalog

Thomas Eiter, Georg Gottlob, Heikki Mannila · ACM Transactions on Database Systems · 1997 · 490 citations · Full text

, , +13

A complexity theoretic approach to randomness

Michael Sipser · 1983 · 470 citations · Full text

, , +13

1–5 of 284

Authors

381

  1. LA
    Lane A. Hemaspaandra

    University of Rochester, United States

    11 publications · 469 citations

    11

    h-index

  2. EH
    Edith Hemaspaandra

    Rochester Institute of Technology, United States

    11 publications · 382 citations

    11

    h-index

  3. LF
    Lance Fortnow

    University of Chicago, United States

    7 publications · 1.3K citations

    7

    h-index

  4. AL
    Alan L. Selman

    University at Buffalo, State University of New York, United States

    7 publications · 306 citations

    7

    h-index

  5. JW
    Johannes Wallner

    TU Wien, Austria

    7 publications · 203 citations

    7

    h-index

1–5 of 381

Institutions

229

  1. TU Wien

    Vienna, Austria

    14 h-index

    38 publications

    1.3K citations

  2. University of Rochester

    Rochester, United States

    10 h-index

    13 publications

    615 citations

  3. University of Helsinki

    Helsinki, Finland

    10 h-index

    17 publications

    1.3K citations

  4. Cornell University

    Ithaca, United States

    10 h-index

    10 publications

    747 citations

  5. Gunma University

    Maebashi, Japan

    8 h-index

    8 publications

    458 citations

  6. Friedrich Schiller University Jena

    Jena, Germany

    7 h-index

    8 publications

    454 citations

  7. Centre National de la Recherche Scientifique

    Paris, France

    7 h-index

    12 publications

    625 citations

  8. University of California San Diego

    San Diego, United States

    6 h-index

    7 publications

    221 citations

1–8 of 229

Venues

  1. SIAM Journal on Computing

    23 publications · 1.8K citations

    18

    h-index

  2. Theoretical Computer Science

    13 publications · 1.1K citations

    13

    h-index

  3. arXiv (Cornell University)

    Repository · 14 publications · 528 citations

    11

    h-index

  4. Journal of the ACM

    JACM · 8 publications · 1.6K citations

    8

    h-index

  5. Journal of Computer and System Sciences

    6 publications · 445 citations

    6

    h-index

1–5