十分睡眠をとっても眠気が抜けない。
関節の怠さから精神的な無気力が生じているような気がする。屈伸やあくびは下等生物でも見られるので太古に形成されたDNAに何か関係あるのかもしれない…。このままでは何もしなくなるだろうという危機感からとりあえずキーボード一つ叩くことから始めて数ヶ月リハビリで記事を書く。(編集画面が新しくなっており非常に使いづらい)
pnp問題のv2を以前投稿をしたのでそれについて
探索者は答えを知らない状況から問題を解こうとする。
判定者は答えを知っているアドバンテージがある。そして答えが正しいかの確認作業をする。
その確認作業が多項式時間で可能な問題は、探索者もまた必ず多項式時間で解けるかどうかというのが
pnp問題だったと思う。
v2の比較判定問題では特定のアルゴリズムは想定しておらず、一回にどれくらい判定可能なアルゴリズムなのかという抽象的な設定を置いている。
最も優れたアルゴリズムは一回の判定で解を得られるものである。
判定者が一回の判定で解を得られるアルゴリズムを探索者も使うことを想定する。
このとき単独判定問題と同様に、計算量オーダーの次元が異なっており、多項式時間で確認できる問題が問題の難しさに関係しているようには考えにくいという内容です。
具体的にはp.5 section 1.2.3 1:n 比較値を例に挙げると
判定者は「Fが最も重いか？」という入力に対して一回の判定でtureを出力するアルゴリズムを仮定する。
そのアルゴリズムを探索者が用いるのであるが解が不明なため、まず「Aが最も重いか？」という入力から行い、falseの出力を得る。次いでB、C・・・と判定してゆくことになる。
つまり判定者の計算量オーダーΟ(1)が、その次元を隔てた探索者の計算量オーダーに影響していないという印象を受けます。
shitetsuronnkou blog 