Concepedia

P-completeness

P-Completeness is the property of a decision problem that is complete for the complexity class P under deterministic logarithmic-space reductions, meaning it is among the hardest problems in P such that any problem in P can be reduced to it in logarithmic space.

62

Publications

3.6K

Citations

114

Authors

65

Institutions

Publications per year

2017–2026

8

Parents

Publications

62

On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines

Lenore Blum, M. Shub, Steve Smale · Bulletin of the American Mathematical Society · 1989 · 1.1K citations · Full text

, , +17

On Isomorphisms and Density of $NP$ and Other Complete Sets

L. Berman, Juris Hartmanis · SIAM Journal on Computing · 1977 · 460 citations

, , +15

Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues

Karl A. Abrahamson, Rodney G. Downey, Michael R. Fellows · Annals of Pure and Applied Logic · 1995 · 158 citations

, , +11

Vector finite elements for electromagnetic field computation

Z.J. Cendes · IEEE Transactions on Magnetics · 1991 · 137 citations

, , +14

Linear programming is log-space hard for P

David Dobkin, Richard J. Lipton, Steven P. Reiss · Information Processing Letters · 1979 · 120 citations

, , +12

1–5 of 62

Authors

114

  1. ME
    Matthias Ehrgott

    University of Auckland, New Zealand

    2 publications · 199 citations

    2

    h-index

  2. TL
    Thomas Lengauer

    Max Planck Institute for Informatics, Germany

    2 publications · 100 citations

    2

    h-index

  3. KW
    Krzysztof Wojtas

    AGH University of Krakow, Poland

    2 publications · 33 citations

    2

    h-index

  4. SM
    Satoru Miyano

    The University of Tokyo, Japan

    2 publications · 49 citations

    2

    h-index

  5. RE
    Robert E. Tarjan

    Princeton University, United States

    2 publications · 100 citations

    2

    h-index

1–5 of 114

Institutions

65

  1. University of Kaiserslautern

    Kaiserslautern, Germany

    2 h-index

    2 publications

    199 citations

  2. The University of Texas at Austin

    Austin, United States

    2 h-index

    2 publications

    81 citations

  3. Rutgers, The State University of New Jersey

    New Brunswick, United States

    2 h-index

    2 publications

    61 citations

  4. University of Rochester

    Rochester, United States

    2 h-index

    2 publications

    41 citations

  5. AGH University of Krakow

    Krakow, Poland

    2 h-index

    3 publications

    48 citations

  6. Stony Brook University

    Stony Brook, United States

    1 h-index

    2 publications

    50 citations

  7. Rochester Institute of Technology

    Rochester, United States

    1 h-index

    1 publications

    24 citations

  8. Ghent University

    Ghent, Belgium

    1 h-index

    4 publications

    60 citations

1–8 of 65

Venues

  1. SIAM Journal on Computing

    3 publications · 569 citations

    3

    h-index

  2. 2

    h-index

  3. Computational Complexity

    CC · 2 publications · 35 citations

    2

    h-index

  4. Artificial Intelligence

    2 publications · 120 citations

    2

    h-index

  5. Pacific Journal of Mathematics

    2 publications · 35 citations

    2

    h-index

1–5