P问题

（计算机科学术语）

P问题是具有多项式算法的判定问题。这里的P代表Polynomial。P问题就是可以有一个确定型图灵机在多项式时间内解决的问题。即那些存在O（n）， O（nk）， O（nlogn）等多项式时间复杂度解法的问题。比如排序问题、最小生成树、单源最短路径。直观的讲，我们将P问题视为可以较快解决的问题。P问题（P-problem）具有多项式算法的判定问题。这里P表示Polynomial一词的第一个字母。