Polynomial-time reduction

deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time. Foundations of Computational Mathematics. 2016,. to

換句話說，一個問題X屬於NP-易，若且唯若存在某個在NP裡面的問題Y，令X可以於多項式時間內圖靈歸約（polynomial-time Turing reducible）至Y。換句話說，給予一個解決Y的神諭（一個只需要單位時間就可以），則存在一個在多項式時間內解決X的

依照上述NPC的定義，所謂的歸約（reduce to）其實是多項式時間多對一變換的簡稱。 另一種歸約法稱為多项式时间图灵归约（polynomial-time Turing reduction）。若我們提供一個副函式（subroutine）可以在多項式時間解出"Y"，又可寫出呼叫此副函式的程式並在多項式時間解

在计算複杂度理论内，RL（Randomized Logarithmic-space，随机对数空间），或者说RLP（Randomized Logarithmic-space Polynomial-time，随机对数空间多项式时间），是一个複杂度类，包含能以概率图灵机，在对数空间与多项式时间之内，在仅有单向容错的状况内解决的问题。此命名法

式的不定元），那么我们称这类问题的集合为P（polynomial time Turing machine）。而将前述定义中的“确定性图灵机”改为“不确定性图灵机”，那么所得到的问题集合为NP（non-deteministic polynomial time Turing machine）。类似的，设