A Compendium of Problems Complete for P (Preliminary)

• Author(s) / Creator(s)

  • Greenlaw, Raymond
  • Ruzzo, Walter L.
  • Hoover, James

• Technical report TR91-11. This paper serves two purposes. Firstly, it is an elementary introduction to the theory of P-completeness - the branch of complexity theory that focuses on identifying the problems in the class P that are \"hardest\" in the sense that they appear to lack highly parallel solutions. That is, they do not have parallel solutions using time polynomial in the logarithm of the problem size and a polynomial number of processors unless all problem in P have such solutions, or equivalently, unless P = NC. Secondly, this paper is a reference work of P-complete problems. We present a compilation of the known P-complete problems, including several unpublished or new P-completeness results, and many open problems. | TRID-ID TR91-11

• Date created

  1991

• Subjects / Keywords

  • Complexity theory
  • P-completeness

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R39Z90F7X

• License

  Attribution 3.0 International