言語PERMPOW={(p, q, t) | p, q は 長さkの置換 ∧ pt = q ∧ tは2進整数}がクラスPに属すること、すなわちあるが与えられたときに かどうかの判別が多項式時間で行えることを示します。
次の判定アルゴリズムAを考えます。
for i 1 to size(t):
上記アルゴリズムでは、tを上位の桁から見ていくことで計算回数を節約しています。プログラムの構造としては数字列のパースに似ているかもしれません。
ループが回で、の右から桁目を見るのに、置換の適用にかかるので全体ではかかりますが、これは多項式時間に収まっているので、が証明できました。