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.
P-Problem
See also
Complexity Theory, NP-Complete Problem, NP-Hard Problem, NP-Problem, P Versus NP Problem, Property PExplore 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." 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.Referenced on Wolfram|Alpha
P-ProblemCite this as:
Weisstein, Eric W. "P-Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/P-Problem.html