P (複雜度)多項式時間內確定性圖靈機可解決的計算複雜度問題。 / 維基百科,自由的 encyclopedia 在計算複雜度理論中,P(polynomial time class)是在複雜度類別問題中可於確定型圖靈機以多項式量級(或稱多項式時間)求解的決定性問題。 複雜度關係韋恩圖 P通常表示那類可以「有效率地解決」或「溫馴」的可計算型問題,就算指數級非常高也可以算作「溫馴」,例如RP與BPP問題。當然P類別存在很多現實處理上一點也不溫馴的問題,例如一些至少需要n1000000指令來解決的問題。很多情況下存在著更難的複雜度問題
在計算複雜度理論中,P(polynomial time class)是在複雜度類別問題中可於確定型圖靈機以多項式量級(或稱多項式時間)求解的決定性問題。 複雜度關係韋恩圖 P通常表示那類可以「有效率地解決」或「溫馴」的可計算型問題,就算指數級非常高也可以算作「溫馴」,例如RP與BPP問題。當然P類別存在很多現實處理上一點也不溫馴的問題,例如一些至少需要n1000000指令來解決的問題。很多情況下存在著更難的複雜度問題