پ (تعقيد)
في نظرية التعقيد التحسيبي، يعتبر پي 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 .
- Sipser, Michael (2006). Introduction to the Theory of Computation. Course Technology Inc. ISBN . Section 7.2: The Class P, pp. 234-241.
روابط خارجية
- نطقب:CZoo
- نطقب:CZoo
