This decommissioned ERA site remains active temporarily to support our final migration steps to https://ualberta.scholaris.ca, ERA's new home. All new collections and items, including Spring 2025 theses, are at that site. For assistance, please contact erahelp@ualberta.ca.
- 577 views
- 2108 downloads
A Compendium of Problems Complete for P (Preliminary)
-
- Author(s) / Creator(s)
-
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
-
- Type of Item
- Report
-
- License
- Attribution 3.0 International