什麼是p問題

P問題是一類可以在多項式時間內解決的判定問題。

這類問題可以用確定性算法在多項式時間內判定或解出，例如排序問題、最小生成樹問題和單源最短路徑問題。簡單來說，如果一箇問題存在O(n)、O(nk)、O(nlogn)等多項式時間複雜度的解法，那麼它就被歸類爲P問題，其中“P”代表“多項式”（Polynomial）。在計算複雜度理論中，多項式時間指的是問題的計算時間m(n)不大於問題大小n的多項式倍數。