クラスPSPACEがクラスNPより巨大であることの直感的な説明

この記事の目的

ザード様は知っての通り頭が悪いので、
計算量理論におけるP < NP < PSPACEの関係のうち
NP < PSPACEがずっと理解できないでいた

…何で莫大な時間をかけないと計算できない問題よりメモリをたかだか多項式量使うだけの問題のほうが難しいのだ？

最近やっとPSPACE > NPの気持ちが分かったのでメモも兼ねて記載

…というかタイトルを
クラスPSPACE > クラスNPであることの直感的な説明
にしたらクラスPSPACE > クラスNPがサニタイジングされたぞ？？ noteってポンコツじゃねえ？

クラスPSPACE > クラスNPの気持ち

これに関してはクラスPSPACEに分類される問題を多項式時間で解く、具体的なアルゴリズムを想像すると早い

予め全パターンのテーブルを用意しておけば、テーブルの探索時間で問題は解ける、つまり線形時間で問題は解ける

クラスPSPACEが言っているのはただこれだけである

確かに巡回セールスマン問題だろうがなんだろうが、クラスNP程度であれば全パターンのテーブルを作ってしまえば空間の使用量はたかだか多項式で抑えられるし、メモリさえ許せば多項式時間で解くことが可能である、当たり前の話である

たとえば将棋は

盤のサイズ＝有限
駒の数＝有限

なので出現する局面はたかだか有限である

つまり、盤上の駒の配置と持ち駒とその時の正解の手を全パターンテーブルに持ってしまえば後は(ものすごく巨大とはいえ)たかだか多項式サイズのそのテーブルの探索で最善手を常に判定できるようになる

これが将棋がクラスPSPACEであることの直感的な証明である

考察

じゃあ機械学習はどうなる？

なんか学習方法とか深層学習の理論(そもそも何故多層化でうまく行った？)とかをみんなで頑張って研究しているけれども、機械学習のやっていることは要はただのIF全パターンの書き出しに過ぎない

ただ単に昔はエキスパートシステムとか言って人力でIF文全パターンを書き出す「AI」があったが、今では技術の進歩でそのIF文全パターン自体を学習のプロセスを通して自動で書き出してくれるようになったに過ぎない

じゃあここで問題が生じる

その機械学習が書き出したIF文全パターンの空間のサイズが指数関数的になった場合、正しく学習を終えたAIでも実行時に探索が終わらず半永久的に最適解を求められないのではないか

つまり、機械学習で(無限の精度で)近似解を出せるのはクラスPSPACEの問題までで、クラスEXPTIMEより上の問題には対応できないのではないか

特に囲碁はクラスEXPTIMEの計算量のゲームであることが知られている
つまりアルファ碁は膨大なパターンを覚えたけれども、それは(枝刈りを駆使するとしても)たかだか線形時間で探索が終わる範囲しか調べていないのではないか

囲碁のパターンの学習には指数関数的なサイズのメモリが必要だとすると、それを機械学習でAIに覚えさせることに成功したとしても、AIの思考が終わらなくなってしまう

つまり人類はまだ囲碁のことをなにもわかっていないのではないか

結び

書きたいこと全部書いたので終わり