多項式時間近似スキーム
PTASを持たない問題が、PTASと似通った特徴を持つ多項式時間乱択近似スキーム(PRAS)を持つことがある。PRASは最適化問題のインスタンスとパラメータ ε > 0 {\displaystyle \varepsilon >0} を入力とし、多項式時間で『高い確率』で最適解の 1 + ε {\displaystyle 1+\varepsilon } 倍以下のソリューションを生成することのできるアルゴリズムである。『高い確率』とは慣習的に 3 / 4 {\displaystyle 3/4} 以上のことであるが、ほとんどの確率的計算複雑度のクラスは、この具体的な値に対してロバストである。PTASと同様にPRASは問題のサイズ n {\displaystyle n} に対して多項式の計算時間を持たねばならないが、 ε {\displaystyle \varepsilon } に対してはそうではない。 ε {\displaystyle \varepsilon } に対するEPTASと同様の制約を持つものを効率的多項式時間乱択近似スキーム(EPRAS)と呼ぶ。また、FPTASと同様の制約を持つものを完全多項式時間乱択近似スキーム(FPRAS)と呼ぶ。