Concepedia

P Versus Np Problem

The "P Versus NP Problem" is a fundamental open question in computational complexity theory that asks whether every decision problem for which a solution can be verified in polynomial time by a deterministic Turing machine (NP) can also be solved in polynomial time (P).

42

Publications

2.7K

Citations

64

Authors

54

Institutions

Publications per year

2017–2026

4

Variants

P Vs NpP Vs Np Problem

Parents

Publications

42

The status of the P versus NP problem

Lance Fortnow · Communications of the ACM · 2009 · 325 citations

, , +12

On Limited Nondeterminism and the Complexity of the V-C Dimension

Christos H. Papadimitriou, Mihalis Yannakakis · Journal of Computer and System Sciences · 1996 · 200 citations

, , +15

The history and status of the P versus NP question

Michael Sipser · 1992 · 172 citations

, , +6

Improving Exhaustive Search Implies Superpolynomial Lower Bounds

Ryan Williams · SIAM Journal on Computing · 2013 · 160 citations

, , +14

Algebrization

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

, , +17

1–5 of 42

Authors

64

  1. LF
    Lance Fortnow

    University of Chicago, United States

    3 publications · 362 citations

    3

    h-index

  2. SA
    Scott Aaronson

    Massachusetts Institute of Technology, United States

    3 publications · 279 citations

    3

    h-index

  3. KM
    Ketan Mulmuley

    University of Chicago, United States

    3 publications · 106 citations

    3

    h-index

  4. RW
    Ryan Williams

    Stanford University, United States

    2 publications · 239 citations

    2

    h-index

  5. AW
    Avi Wigderson

    Hebrew University of Jerusalem, Israel

    2 publications · 220 citations

    2

    h-index

1–5 of 64

Institutions

54

  1. University of Toronto

    Toronto, Canada

    3 h-index

    4 publications

    226 citations

  2. Massachusetts Institute of Technology

    Cambridge, United States

    3 h-index

    3 publications

    322 citations

  3. AT&T (United States)

    Bedminster, United States

    3 h-index

    4 publications

    516 citations

  4. IIT@MIT

    Cambridge, United States

    2 h-index

    2 publications

    139 citations

  5. IBM Research - Almaden

    San Jose, United States

    2 h-index

    2 publications

    239 citations

  6. University of Chicago

    Chicago, United States

    2 h-index

    4 publications

    87 citations

  7. University of California, Berkeley

    Berkeley, United States

    2 h-index

    2 publications

    80 citations

  8. University of California San Diego

    San Diego, United States

    2 h-index

    3 publications

    441 citations

1–8 of 54

Venues

  1. Journal of the ACM

    JACM · 3 publications · 185 citations

    3

    h-index

  2. ACM Transactions on Algorithms

    TALG · 2 publications · 89 citations

    2

    h-index

  3. Communications of the ACM

    2 publications · 350 citations

    2

    h-index

  4. Applied Mathematics and Computation

    1 publications · 16 citations

    1

    h-index

  5. European Review

    1 publications · 14 citations

    1

    h-index

1–5