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 n, where n is the length of the input.

See also

Complexity Theory, NP-Complete Problem, NP-Hard Problem, NP-Problem, P Versus NP Problem, Property P

Explore with Wolfram|Alpha


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.", S. "The P versus NP Problem.", 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.

Referenced on Wolfram|Alpha


Cite this as:

Weisstein, Eric W. "P-Problem." From MathWorld--A Wolfram Web Resource.

Subject classifications