言語PERMPOW={(p, q, t) | p, q は 長さkの置換 ∧ p^t = q ∧ tは2進整数}がクラスPに属すること、すなわちあるが与えられたときに かどうかの判別が多項式時間で行えることを示します。

次の判定アルゴリズムAを考えます。

上記アルゴリズムでは、tを上位の桁から見ていくことで計算回数を節約しています。プログラムの構造としては数字列のパースに似ているかもしれません。

ループが回で、の右から桁目を見るのに、置換の適用にかかるので全体ではかかりますが、これは多項式時間に収まっているので、が証明できました。