PERMPOWがクラスPに属することの証明
言語PERMPOW={(p, q, t) | p, q は 長さkの置換 ∧ pt = q ∧ tは2進整数}がクラスPに属すること、すなわちあるが与えられたときに かどうかの判別が多 2019-07-17 14:32:18 Author: furutsuki.hatenablog.com(查看原文) 阅读量:102 收藏

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

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

  1. 恒等置換 r = {1, 2, 3, ..., k} を用意する

  2. for i 1 to size(t):

    1. r に rを適用する
    2. もし tの左からi桁目が1ならr に pを適用する
  3. rとqが等しければ w \in PERMPOWであり、違うなら w \not \in PERMPOW

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

ループが size(t)回で、 tの右から i桁目を見るのに O(size(t))、置換の適用に O(k)かかるので全体では O({size(t)}^2)かかりますが、これは多項式時間に収まっているので、 PERMPOW \in Pが証明できました。


文章来源: https://furutsuki.hatenablog.com/entry/2019/07/17/143218
如有侵权请联系:admin#unsafe.sh