多項式時間 多項式時間英語Polynomial time在計算複雜度理論中指的是一個問題的計算時間 m  n  displaystyle mn 不大於問題大小 n displaystyle n 的多項式倍數任何抽象機器都擁有一複雜度類此類包括可於此機器以多項式時間求解的問題 以數學描述的話則可說 m  n   displaystyle mn O  n k  displaystyle nk 此 k displaystyle k 為一常數值依問題而定 數學家有時把如多項式時間長的演算法視為快速計算相對應的是超多項式時間表示任何多項式時間的輸入數目只要夠大超多項式時間所需的解題時間終究會大大超過任何多項式時間的問題指數時間就是一例 可以在決定型依序機器上例如圖靈機以多項式時間解決的決定性問題其屬於的複雜度類被稱為P可以在多項式時間驗證答案的決定性問題稱為NP而NP也是可以在非確定型圖靈機以多項式時間解決的問題NP兩字為Nondeterministic Polynomial的縮寫 多項式時間在決定型機器上是最小的複雜度類別且在機器模型改變時依舊強韌且也是可在副程式組合過程中保持封閉的類別 強多項式時間指的是此問題的運算時間不因輸入資料的數字大小而變動而是依照輸入資料的結構複雜度例如图论中的頂點數量