پ (تعقيد)
في نظرية التعقيد التحسيبي، يعتبر پي P، الذي يعرف أيضاً ب PTIME أو DTIME(nO(1))، أحد الأصناف الأساسية للتعقيد، إذ يضم كل مسائل القرار التي يمكن حلها باستخدام آلة تورنگ قطعية باستخدام مقدار حدودي حدودي من الزمن التحسيبي أو كما يقال باستخدام زمن حدودي.
Cobham's thesis holds that P is the class of computational problems which are "efficiently solvable" or "tractable"; in practice, some problems not known to be in P have practical solutions, and some that are in P do not, but this is a useful rule of thumb.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
مراجع
- Cobham, Alan (1965). "The intrinsic computational difficulty of functions". Proc. Logic, Methodology, and Philosophy of Science II. North Holland.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 34.1: Polynomial time, pp. 971-979.
- Papadimitriou, Christos H. (1994). Computational complexity. Reading, Mass.: Addison-Wesley. ISBN 0-201-53082-1.
{{cite book}}: Cite has empty unknown parameter:|coauthors=(help) - Sipser, Michael (2006). Introduction to the Theory of Computation. Course Technology Inc. ISBN 0-619-21764-2.
{{cite book}}: Cite has empty unknown parameter:|coauthors=(help) Section 7.2: The Class P, pp. 234-241.