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.

See also

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

Explore with Wolfram|Alpha

References

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." https://www.claymath.org/millennium/p-vs-np/.Cook, S. "The P versus NP Problem." https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.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.

Referenced on Wolfram|Alpha

P-Problem

Cite this as:

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

Subject classifications