A compendium of problems complete for P

@misc{citeulike:94778, abstract = {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...}, author = {Greenlaw, R. and Hoover, H. and Ruzzo, W. }, citeulike-article-id = {94778}, keywords = {algorithms, complexity, reference}, posted-at = {2005-02-15 05:24:27}, priority = {2}, title = {A compendium of problems complete for P}, url = {http://citeseer.ist.psu.edu/greenlaw91compendium.html}, year = {1992} }

TY - GEN ID - citeulike:94778 L3 - citeulike-article-id:94778 N2 - 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... TI - A compendium of problems complete for P KW - algorithms KW - complexity KW - reference AU - Greenlaw, R AU - Hoover, H AU - Ruzzo, W PY - 1992/// UR - http://citeseer.ist.psu.edu/greenlaw91compendium.html ER -