为了评价一个算法的优劣, 人们用该算法所需步骤相对于问题的大小的函数为检测标准。 假设问题大小用N表示,算法的计算步骤为N*N, 则该算法为平方算法。
通常能够实际使用的算法应该不高于多项式, 即 Polynomial。 P 代表所有能用多项式算法解决的问题。 所有已经证明没有Polynomial 算法的问题属于高阶P。 NP是一大类问题, 目前没有Polynomial算法可又无法证明它们没有Polynomial解法。 但如果能借助上帝之手(Oracle) 猜出结果,则可以有Polynomial算法。 计算理论的一大难题就是 P是否等于NP。
这个理论系多伦多大学计算机系的一个教授提出, 他因此而获得计算机图灵奖。