計算量理論入門

前回までの復習から始めると、まず読み込みに加え書き込む機能が加わった有限状態機械のことをチューリング機械と呼びました。言語を1文字ずつ読み書きしていくという単純な仕組みのチューリング機械がなぜそれほど大事かといえば、ほかにれっきとした「計算モデル」としての資格があるもの -- たとえば、再帰関数やラムダ計算 -- で認識できる言語はすべて「認識可能」のクラスに属する (= モデルがチューリング機械と等価になる) ことが知られているからです。

したがって、チューリング機械は一見シンプルな仕組みをしているものの、情報処理 -- 計算をするということ -- の本質に迫るような仕組みだといえるのです。

実際、この

計算できるということ $~~~ \Longleftrightarrow ~~~$ チューリング機械で認識可能

という壮大な橋渡しには Church–Turing thesis という名前の '予想' が立てられています。

さて、3日目の講義では「多項式時間」という考え方を導入します。これはだいたい '現実的な' 時間で計算可能かどうかを示すもので、チューリング機械の技術的な定義の詳細 (ex: テープの形、読み込んだときの処理) は多項式時間での解決可能性に影響を与えないことから、したがって問題の解決が '現実的かどうか'*1 ということに限らず、問題の複雑さを量る本質的な尺度だとして重要視されています。

問題の例として、与えられた n 桁の自然数 k は素数かどうか判定するものを考えると、これは 1 < m < k について全て調べることにすると、10ⁿ 個ほどある候補をすべて試すのには指数時間かかります -- が、2002年になんと多項式時間で判定する方法が見つかったそうです (!):

en.wikipedia.org

また、チューリング機械と多項式時間という2つの概念を使って説明できるのが $\rm{P} \neq \rm{NP}$ 予想とよばれる主張で、これは連続講義中で取り扱った言葉でいえば

$\delta : Q \times \Sigma \rightarrow ( Q \times \Sigma \times {左, 右}) \cup {止}$ という多価の遷移関数を持つ non-deterministic なチューリング機械によって多項式時間で解ける問題のクラス (= 'NP') は CE クラス (= 'P', 多項式時間のチューリング機械で認識可能な言語の全体) に等しいか?

-- しかし、これらの用語は [非常に大雑把ながら] わかる一方で、これが実際の研究でどういう応用や意味合いを持っているかについてはまだ自分の理解が至っていません。

それでも、一般的に有名だとされる問題であるほど、少し足を延ばして背後の数学的なモチベーションを知るのはとても気分のいいことだと思います

Frobenius 写像の周辺

前回は原始根という概念を定義し、 $\mathbb{Z}$ について観察された現象が $\mathbb{F}_{f(X)}$ においても成立することを確認しました。今回は有限体上のガロア理論を考えたいということで、そこからはじめます。

f:id:zeta_aniki:20210804214436p:plain — *Galois Theory over 𝔽_f(X).*

-- ここで $m$ は $d$ の約数。

やはりね、パスカルの三角形とか 3b1b の映像作品*2をはじめ、ビジュアル (= 視覚的な美しさ) というものは感動にすごく本質的だと思う*3 -- そういうわけで、自分がむかし「対応」(correspondence) という現象に惹かれていたのも、おそらく偶然ではない

さて、連続講義の introduction にもある通り、Frobenius 写像は有限体の Galois 理論において大切な役割を果たし、この延長線上には Weil 予想という数論幾何の有名な予想があります。これは、(3時間目で勉強している) 代数多様体とよばれる図形 -- たとえば

$X^n + Y^n = Z^n$

-- について、[位相的な] コホモロジーという不変量を用いて $\mathbb{F}_{q}$ 上の解の個数を求めることを試みます。(Frobenius 写像の '固定点' というのがどういうものなのかまだよくわからないので、「有理点」という概念を別の視点から観察することの実感はまだ湧きません。)