info prev up next book cdrom email home


A problem is assigned to the P (Polynomial time) class if the number of steps is bounded by a Polynomial.

See also Complexity Theory, NP-Complete Problem, NP-Hard Problem, NP-Problem


Borwein, J. M. and Borwein, P. B. Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity. New York: Wiley, 1987.

Greenlaw, R.; Hoover, H. J.; and Ruzzo, W. L. Limits to Parallel Computation: P-Completeness Theory. Oxford, England: Oxford University Press, 1995.

© 1996-9 Eric W. Weisstein