A problem is assigned to the P (polynomial time) class if there exists at least one algorithm to solve that problem, such that the number of steps of the algorithm is bounded by a polynomial in , where is the length of the input.

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

Clay Mathematics Institute. "The P vs. NP Problem." http://www.claymath.org/millennium/P_vs_NP/.

Cook, S. "The P versus NP Problem." http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf.

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

Smale, S. "Mathematical Problems for the Next Century." Math. Intelligencer 20, No. 2, 7-15, 1998.

Smale, S. "Mathematical Problems for the Next Century." In Mathematics: Frontiers and Perspectives 2000 (Ed. V. Arnold, M. Atiyah, P. Lax, and B. Mazur). Providence, RI: Amer. Math. Soc., 2000.

CITE THIS AS:

Weisstein, Eric W. "P-Problem." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/P-Problem.html