はてぃーぽったーの備忘録

某授業まとめ+競プロの感想記事

チューリング認識不可能な言語と対角線論法

情報数学 数学

目次

概要

今回は以下に示す言語が判定不可能であり、その補集合が認識不可能であることを示していきます。

A_{TM} = \{\langle M, w\rangle | M はチューリング機械で w を受理する\}

その次に、証明に関連して対角線論法について説明します。

判定不可能な言語

上記の A_{TM} が判定不可能なことは以下のような手順で示せます。

証明

  • 以下のような挙動をする TM H を考える。この H が実際には存在しないことを示せれば A_{TM} が判定不可能であると示せる。
  1. H(\langle M, w\rangle) = 受理（M が w を受理する時）
  2. H(\langle M, w\rangle) = 拒否（M が w を受理しない時）
  • この H を用いる TM D を考える。 D は TM M のコード化 \langle M \rangle を入力として、 H に対して \langle M, \langle M\rangle\rangle を走らせる。そうして得られた出力の逆を D は出力する。つまり、 D の挙動は以下のようになる。
  1. D(\langle M\rangle) = 受理（M が \langle M\rangle を受理しない時）
  2. D(\langle M\rangle) = 拒否（M が \langle M\rangle を受理する時）
  • その時の挙動を記述すると
  1. D(\langle M\rangle) = 受理（D が \langle D\rangle を受理しない時）
  2. D(\langle M\rangle) = 拒否（D が \langle D\rangle を受理する時）
  • つまり D(\langle D\rangle) が受理でもあり拒否でもあることとなり、矛盾する

対角線論法を用いてこの定理は証明されていますが、それについては後述します。

さて、 A_{TM} が判定不可能であることが示されました。次に、以下の定理を示します。

  • 任意の言語に対し、言語とその補集合がどちらも Turing 認識可能であるときに限り、その言語は判定可能である。

これが示せると、対偶を取ることにより

  • 言語 A が判定不可能で認識可能 \Rightarrow A^C （ A^C は A の補集合）が認識不可能

であることが示せます。

証明

示すべきことは二つあります。

  1. 言語が判定可能なら、その言語と補集合はどちらも認識可能
  2. 言語とその補集合がどちらも認識可能なら、その言語は判定可能

1 は明らかです（判定の方が認識より厳しい条件です）。

2 を示します。言語 A を認識する TM を M_1、 A^C を認識する TM を M_2 とします。これらを使用して以下の挙動をする 2 テープ TM M を考えます。

  • M は入力 w に対して
  1. 並列に M_1 と M_2 の両方を動作させる。
  2. M_1 が受理するならば M は w を受理し、 M_2 が受理するならば拒否する。

M_1 と M_2 のどちらか一方は必ず w を受理し、受理の定義からそれは有限時間内に起こるので M は必ず停止します。 w\in A であれば M は受理し、それ以外は拒否するので M は A に対する判定装置となっています。よって、 A が判定可能なことが示せました。

 

以上の証明により、（ A_{TM} が Turing 認識可能なので） A_{TM}^{C} が Turing 認識不可能な言語であることが示せました。

対角線論法

対角線論法の話に入る前に、写像について簡単に復習しておきます。

A, B を集合とした時、任意の A の要素 a に対し、それに対応する B の要素 f(a) をただ一つ対応付けることを考えます。このとき、 f のことを A から B への写像と言います。また、写像の全射及び単射については以下のように定義されます。

  • a, a'\in A,\ f(a)=f(a') \Rightarrow a = a' が常に成り立つとき、 f は単射であるという。
  • 任意の b\in B に対し、 a\in A が存在し、 b = f(a) となるとき、 f は全射であるという。

よって、以下のことが言えます。

  1. f が全射 \Rightarrow A の大きさは B 以上
  2. f が単射 \Rightarrow B の大きさは A 以上

「大きさ」というかなり怪しい表現をしましたが、有限集合に限定すればここでいう大きさとは集合内の要素の個数を指しています（無限集合に関しては濃度という概念を適宜参照してください）。

 

さて、対角線論法は一般的な背理法のテクニックとして知られています。具体例の一つとして無限集合同士の大きさの比較に役立ちます。以下、簡単に集合 X と冪集合 2^X の大きさが異なることを示します。大きさが異なることを示すのには、いかなる写像 \psi によっても 2^X のある要素に飛ぶような X の要素が取れないことを言えば良いです。厳密に書き下すと以下のようになります。

  • \psi: X\to 2^X を写像、Y=\{x\in X|x\notin\psi(x)\} とするとき、\psi(x)=Yとなるx\in X は存在しない

証明

背理法により示す。 \psi(x)=Y となるような x\in X の存在を仮定する。

x\in Y とすると仮定より x\in \psi(x) でもあるが、これは Y の定義に矛盾する。 x\notin Y とすると x\notin \psi(x) でもあるが、これも Y の定義に矛盾する。よって示された。

 

集合の大きさを比べる時に、写像 \phi の全射性、単射性を使うことは非常によくあります。これをもっと対角線っぽくした具体例が \mathbb{R} が非可算であることの証明です。 \mathbb{N}\to\mathbb{R} となる全単射の写像が作れないということを、小数点以下の各桁で n=1, n=2,\dots と異なるものを取ってくることで示しています（この辺は画像で見た方が分かりやすいですが）。

高校数学の美しい物語というサイトではより直接的に上記の定理を行列を用いて言い換えています。

カントールの定理の証明と対角線論法 | 高校数学の美しい物語

（こういうのって勝手に貼っていいものなんでしょうか）

 

\Sigma 上の TM は可算個であり、 \Sigma 上の言語全体の集合 2^{\Sigma^*} が非可算個、各 TM に対してそれが認識する言語を対応させる写像 L が単射であることを考えると、チューリング認識不可能な言語が存在すること自体は直感的に理解できるかと思います（詳細に証明しようと思ったら、 \mathbb{R} が非可算であることの証明から書くことになると思います）。

 

参考資料

 計算理論の基礎2 計算可能性の理論, 著: Micheal Sipser

カントールの定理の証明と対角線論法 | 高校数学の美しい物語

WUPC2020-D Treasure Mountains で群論をつまみ食いする

競技プログラミング 数学

久しぶりの更新です. 今回は先日 AOJ 上で開催された早稲田大学プログラミングコンテスト 2020 の D 問題の思考フローに伴い, 群論を軽くつまみ食いしようと思います. （簡単のため, 定理等の詳細な説明を省いたり, 厳密性を欠く記述が見受けられると思いますがご了承ください, 致命的な誤りがあればご指摘いただけると幸いです）

問題はこちら

https://onlinejudge.u-aizu.ac.jp/beta/room.html#WUPC2020/problems/D

概要: 
N+1 が素数となるような N\geq 4が与えられる
tを長さMの数列\{d_M\}を使って暗号化（各d_iはNと互いに素）
tを数aで暗号化...t\mapsto t^a\hspace{2mm} mod\hspace{1mm} N+1
各クエリx,y,z:\hspace{1mm} tをd_y,d_{(y+1) \% M},...,d_{(y+z-1) \% M}で暗号化した結果xになるとき, tを出力

考えたこと:

暗号化が完了した結果は t^{d_yd_{(y+1)\%M}...d_{(y+z-1)\%M}}=xなので, xに tの指数（ kとする）の乗法逆元乗をしてあげればいい（日本語さん…）. 実はここに「 各d_iはNと互いに素 」が効いてくる.

 

まずは問題の整理をしましょう. この問題で解決しなければならない問題は大きく分けて二つあります.

  1. k=d_yd_{(y+1)\%M}...d_{(y+z-1)\%M}の計算
  2. k^{-1}の存在性および計算

1. はまず zが大きいので一回のクエリで数列 \{d_M\}を何周もする可能性があり, 累積積を使うなどの工夫が必要です. しかし問題はそれだけでなく, kが非常に大きくなることから, \mathbb{Z}上でそのまま計算することができません. ここでも何らかの工夫が必要です.

2. は k^{-1}が本当に存在するかという問題です. いつでもあると思うな, 乗法逆元ということです. あとは実際の x^{k^{-1}}の計算ですが, まあこれは繰り返し二乗法でやればいいでしょう. ただmodに気を付ける必要があります.

 

解決したい問題が分かったところで、一旦群の話をします.

群というのはある演算・に対し, 集合 Gの要素について以下の3つが全て成り立つときにその集合のことを群と呼びます.

  1. 単位元 eが存在する. すなわち \forall a\in G に対し, a・e=e・a=a なる e\in G が存在する.
  2. \forall a\in G に対し, a・b=b・a=e となるような b\in G が存在する. この b を a^{-1} と書き, a の（乗法）逆元とよぶ.
  3. \forall a,b,c\in G に対し, (a・b)・c=a・(b・c), つまり結合則が成り立つ.

整数全体の集合 \mathbb{Z}を考えます. 非常に有名な演算であるところの '+'は, 単位元 0, a の逆元 -a, (a+b)+c=a+(b+c) なので +に関して \mathbb{Z} は群をなします.

一方で '×'は, 単位元は1であるものの逆元が一般に存在しません. この掛け算を \mathbb{Z}で考える限り, 2に整数をかけた結果1になるものは無いのです.

これは mod\hspace{1mm} m の世界でもおよそ同じようなことが言えて, 例えば mod\hspace{1mm} 4 の世界では 3 に 3 をかければ 1 になりますが, 2 には何をかけても 1 にはなりません. 

一般に mod\hspace{1mm}m の世界で元 a に対して乗法逆元が存在する必要十分条件は, a と m が互いに素であることです（証明は割愛）. a の逆元は拡張ユークリッドの互除法というアルゴリズムで具体的に求めることが出来ます.

ここまでで書くと, 制約  各d_iはNと互いに素 が嬉しそうだなと感じてきます. なぜなら k=d_yd_{(y+1)\%M}...d_{(y+z-1)\%M} も N と互いに素になるからです. ただ, k^{-1} が mod\hspace{1mm} N での乗法逆元を指すのか, 別の mod での乗法逆元を指すのかはこの段階では分かっていません. もし mod\hspace{1mm}N での逆元が欲しいなら, 問題 2 は解決です.

 

話を群に戻します. 先の説明から, mod\hspace{1mm}m の m が素数である時には m の定数倍以外には乗法逆元が存在することが分かります. このとき, 群の定義から mod\hspace{1mm} m の世界での集合 \{1, 2,\dots, m-1\} は乗法に関して群を成すことが分かります. （単位元の存在と結合則は明らか. 元 a の逆元は ax + my = 1\Leftrightarrow ax = m\times(-y)+1 となる (x,y) を整数全体で求め, その x を mod\hspace{1mm}m で取り直したもの）

以降の記述のため, mod\hspace{1mm}p（pは素数） の世界での集合 \{0, 1,\dots,p-1\} を \mathbb{F}_p とします（この説明はあまり厳密ではないですが, 直感的には以降の説明に差し障りはないと思います）.

 

ここで群の元に対する位数の概念と, 位数に対する重要な定理であるラグランジュの定理を説明します.

定義（群の元の位数）: Gを群, x\in Gとする. もし, x^n=1_Gとなる正の整数が存在すれば, その中で最小のものをxの位数という.

1_G というのは単位元のことです. また, 

定理（ラグランジュの定理）: Gが有限群なら, g\in G の位数は |G| の約数である.

という定理があります. 有限群というのは元の個数が有限であるような群のことを指します. 例えば \mathbb{F}_5 に対する 1 の位数は 1, 2 の位数は 4, 3 の位数は 4, 4 の位数は 2 です. \mathbb{F}_5 - \{0\} は乗法に関して群をなし, 元の個数が 4 なので確かにラグランジュの定理が確かめられました. （ \mathbb{F}_5 自体が 0 という元によって乗法に関して群になれないことに注意です）

ラグランジュの定理から以下のことが言えます.

系（フェルマーの小定理）: x\in \mathbb{F}_pについて, x^{p-1}=1

これは x の位数を n としたときに n\times m = p-1 なる m が存在し, x^{p-1}=x^{n\times m}=1^m=1 となるためです.

さて, 今回は N+1が素数 という制約のもと t\mapsto t^k\hspace{1mm} mod\hspace{1mm}N+1 として暗号化をするのでした. なので t^N=1 が成立し, t^k=t^{k\%N} となります. 

k\%N=k' とします. 残りのやるべきことは \mathbb{F}_{N+1}-\{0\} 上での乗法逆元 k'^{-1} （つまり法を N とした時の乗法逆元）を求め, x^{k'^{-1}} を mod\hspace{1mm}N+1 で計算することです. 前者は拡張ユークリッドの互除法, 後者は繰り返し二乗法で求めることが出来ます. ここで先程挙げていた問題 2 の懸念点が解決されました. 注意としてはあくまで N は素数ではないこと. 乗法逆元を求める手法として, 互除法のほかに法が素数の場合にのみ適用できるものがありますが今回はそれが適用できません. 私はこれで1時間溶かしました...

 

解法のまとめ

よって, この問題を以下のような手順で解くことが出来ました.

  1. 鍵を表す数列 \{d_M\} の累積積を計算する.
  2. k=d_yd_{(y+1)\%M}...d_{(y+z-1)\%M} を, 累積積を用いて mod\hspace{1mm} N で計算する.
  3. k の乗法逆元 k^{-1} を拡張ユークリッドの互除法で求める.
  4. 繰り返し二乗法により x^{k^{-1}} を mod\hspace{1mm}N+1 で計算して出力する.

 

感想

群論の知識を扱うのにとてもいい問題でした. コンテスト中には通せなかったのが悔やまれる... この記事が群論に対してハードルの高さを感じている人に, 学んでみようというきっかけを与えられれば嬉しいです. やってみると楽しいよ！

 

追記: イマイチ分からなかった, という方は以下の記事が非常に要点がまとめられていて非常に分かりやすいと思います. （こういうの勝手に貼っていいのかな）

剰余の乗法の逆元とRSA暗号

参考資料

www.amazon.co.jp

Atcoderで水色になるまでにやったこと

競プロ記事初投稿です.今回はAtCoderで入水するまでにやったことを時系列でまとめていきたいと思います.まずはレートの変遷と累計AC数のグラフを見てみましょう.

f:id:mkwamezaki1007:20191222233835p:plain

レートの変遷

f:id:mkwamezaki1007:20191222233606p:plain

AC数の変遷

僕が競プロを始めたのは1年と半年ほど前です.周りがやってて楽しそうだなーと思ったのが主ですが,コードを書く時間を確保するという側面もありました.大学の講義でコード書く時間はあまり多くないので.

始めた当初は当時の講義で使っていたJavaを使っていましたが,書くのに時間がかかるのとpython書くのにも慣れといたほうがいいのでは,とのことでpython3に乗り換えました.2018年の11月の末の方ですね.この辺りは割とトントン拍子にレートが伸びていきました.自分の周りの友人が早々に入水していったので,このまま自分もそれに続けるだろうと,漠然と思っていました.

 

それがとんでもない間違いだったのです。

 

自分のレートが停滞し始めたのは,令和ABCが始まって間もなくでした.レートの変遷を見ると,7月頃から伸び悩むどころかむしろ縮んでいる時期さえ見て取れます.コンテストに数回出て,パフォがだんだん落ちてくるのを感じました.自分の実力はあまり変わっていないことと参加者のレベルが爆発的に上昇していくことに危機感を覚え,この頃から本格的な精進を始めました.ここから自分がやったことを時系列で挙げていきます.

 

1. AtCoder Scoresを使って300点問題を埋めた + 使用言語をC++に変えた

自分には,精進量も考察力も実装力も何もかも足りていませんでした.とにかく考える時間を増やし,自分の考えをコードで再現する.その作業をひたすらに繰り返しました.

また,使用言語もC++に変えました.pythonだから通せなくてC++なら通せる,ということを経験したことは一度もありませんが,C++ユーザがかなりの割合を占めているという現状から,今後何かと都合のいいことが多いだろうと思い使用言語を変更しました.(なお.今でも小数が絡む問題にはpythonを使うことが多いです) 学んだアルゴリズムとして印象的なのはbit全探索ですかね.当時はまだ全探索が可能ならやる,という意識が無かったので自分の中ではとても革命的な発想でした.

 

それでもレートは上がりません.

 

2. Atcoder Problemsを使って緑difficultyの問題を埋めた

300点を埋め終わって400点問題に差し掛かったころ,AtCoder Problemsに非常に便利な機能が追加されました.それは過去の問題に対して推定難易度を付けるというもので,実際当時の自分には非常に歯応えがあり,かつ頑張れば解けるという問題を効率的に解くことが出来ました.友人の力も借りて,どうにか埋めることが出来たのは夏休みが明けて間もなくのことでした.だんだんと自分に考察力が付いていくのを感じました.この頃から組み合わせの問題を解く時にmod逆元を使い始めた気がします.けんちょんさんの記事を何度も読んで理解に努めました.

 

それでもレートは上がりません.

 

まあでもここまでで上がらないのは予想の範囲内でした.だって水difficultyが解けないのですから,本番で水パフォはなかなか出ません.この頃はまだ自分の停滞に対して楽観的でした.

 

3. Atcoder Problemsを使って水difficultyの問題を埋め始めた 

 この辺りの問題から,探索のコードを書くことが増え,自分の中での探索を始めとした種々のアルゴリズムの書き方が固まってきました.書くことが多かったのは再帰でのdfsとワーシャルフロイド,累積和,めぐる式二分探索(超重要)ですかね.特にdfsは自分の中で書き方をパターン化できるくらいには書いたと思います.あと累積和はStatic Sushiを解くときに,これが累積和を"使いこなす"ってことか…と実感しました.めぐる式にぶたんは言わずもがなと言ったところ.開区間のちからってすげー。

用いた特徴的なデータ構造として記憶に残っているのはUnion-Findぐらいでした.

 

それでもレートは上がりません.

 

4. 水difficultyの問題を埋める一環でデータ構造を履修し始めた + EDPCを始めた

このあたりでいい加減に逃げ続けてきたデータ構造に立ち向かおうということでセグ木を書いてみました.まだコンテストで使ったことはないですが,区間操作についての理解が多少深まりました.

また,dpに関して何も分からん状態だったのでEDPCを徐々に埋め始めました.なかなかdpは他の考察とは毛色が異なるので,集中的に鍛えるのにとても都合が良い教材でした.

 

それでもレートは上がりません.

 

5. コンテスト前にケーキを食べ始める

コンテストを迎えるコンディションに問題があるのでは,という考えに至りました.

とにかくメンタルの弱い私は,落ち着いてコンテストを受けるにはどうしたらいいかを考えました.開始直前にお風呂には入らない,部屋の温度を高くしすぎないなどありますが,特に効果がありそうだと思ったのはコンテスト前にケーキを食べることでした.ケーキを食べることで糖分を補給し,温かいお茶を飲んでリラックスする.もうこれしかないと思いました.

結果はよく分かりませんでした　結果的にこの試みは成功に終わりました.が,この試みを取り入れた後の2回は冷えてしまいました.そしてそのうちの1回(ABC147)で私は…

心が折れかけました.

正直,微増微減はあっても10以上冷えることは無いと思っていました.やることはやってきたと思っていたのですから.

しかし,ABC147の結果は遅解き3完(1155 -> 1141).コンテスト直後は完全にぽっきりいってました.

 

6. 時間に追われて問題を解く

最後にすがったのがこれでした.ABC148が開催されるまでの2週間,私は積極的にバーチャル参加機能を活用してまだ解いていない青diffの問題を含むセットを解いていきました.そこで初めて,自分が"コンテスト時間内に通す感覚"を忘れていたことに気付きました.

 

7. ABC148に参加・全完する

お風呂は30分前に済ませ,M-1を見ながら紅茶とケーキを嗜み,最高にリラックスした状態でコンテストに臨みました.

とにかく誤読には気を付けました.D問題を通した時点で自分の順位は2000位ほど.多少焦りましたが,それでも自分のペースを信じて確実に考察を紙にまとめ,実装していきました.焦るな,落ち着けば時間内に実装できる.二週間前にはそう自分に言い聞かせても無意味だったのでしょうが,バーチャル参加で時間内に解く感覚を思い出したことで落ち着いて考察し,実装のバグを取り除くことが出来ました.FのACの文字列を見た時は,高揚感と安堵,ここまで支えてくれた友人達への感謝など色々な気持ちが入り混じっていました.

 

 

で、結局何をやったんですか

技術面とメンタル面に分けますと,

技術面

bit全探索

mod逆元

dfs, bfs

Union-Find木

累積和

セグ木(まだ使ってないけど)

ワーシャルフロイド法・ダイクストラ法

EDPCを途中まで(執筆時点でKまで埋めている)

考察力を鍛える(考えが煮詰まるまでじっくり考える)

メンタル面

自分の脳がよく回るコンディション(自分の体調および周辺環境)を把握する

これまで時間内に通してきた感覚を頼りに問題を解く

誤読をしないために落ち着いて問題を読む

焦らない

落ち着く

ケーキを食べる

 

こんなところです.この記事を読んで,コンテスト前にケーキを食べる人が増えてくれたら嬉しい限りです. それでは今回はこの辺で.

javafx+sceneBuilderでハマったこととソケット通信でハマったこと

今回私は某大学の某実験において五目並べのGUIアプリを作成しました。一月半という長い間格闘していたわけですが、その中でドツボにハマって時間を溶かした事案を書き連ねていきます。

 

①ObjectInputStreamのインスタンスはObjectOutputStreamのインスタンスを生成した後に生成する

https://stackoverflow.com/questions/14110986/new-objectinputstream-blocks

これはstackoverflowで原因を見つけました。これを見つけ出すのに1日溶けました。南無。原因としてはリンク先に書いてある通りなんですが、ざっくり言うと

・ObjectInputStreamはインスタンス化の際にInputStream（相手側から見たOutputStream）のヘッダ情報を読み取ろうとする

・ObjectOutputStreamを先に生成しないとそのヘッダ情報得るまで待ち続ける

これによりプログラムの実行が止まります。new ObjectInputStream(socket.getInputStream());の前でプログラム止まるんだけど…な人はこれを疑ってみてください。

PrintWriter, BufferedStreamReaderを使う以上はこれは起きないのかも？自分の場合はCUIで原型を作った際にint型配列のオブジェクトの授受をしたかったためObjectOutputStream / ObjectInputStreamを使いましたが, GUI作成の際はあまり必要としなかったので,ここで詰まる人はそんなに多くないのかも。

②コントローラクラスの外側からコントローラクラス内部のメソッドを呼び出してGUI画面に変更を加えようとしても失敗する

これは仕様みたいです。安全性が云々。解決策はPlatform.runLaterでググると出てきます。

③workerスレッド（プログラムのメインな処理を行うスレッド）とapplicationスレッドをちゃんと分けてるはずなのにずっとworkerスレッドに制御が行って画面が操作できない

メインな処理が一度きりならjavafx.concurrent.Task、複数回やるならjavafx.concurrent.Serviceを使いましょう。

④コントローラ内のメソッドってどう呼び出したらいいんだろう

SceneManager（シーン遷移の監督役）内に各シーンのコントローラのインスタンスを保持しておいて、そこにアクセスすればいいかと。

思い出し次第追記していきます。

PとNPのお話および多項式時間還元について(第10回スライド参照)

クラスPとNPについてのお話を試験前最後の記事とさせていただきます。

まず、クラスとは何か。しっかりと定義するのはとてもこの1記事では収まり切りません。そのため、「クラスはものの集まり」程度に思っておいてくれるといいかな、と思います。（あくまで集合とは違うのですが、今回のお話ではそう思っても差支えないと思います）

 

次に、PとNPのお話に入る前に二つの表現形式を定義しておきます。TIME(t(n))とNTIME(t(n))についてです。

t: N → R^{+}を関数とし、

    TIME(t(n))=\{L| LはO(t(n))時間のTMで判定可能な言語\}

NTIME(t(n))=\{L| LはO(t(n))時間の非決定性TMで判定可能な言語\}

では、Pとは何でしょうか。教科書の定義を活用させていただくと、

 

Pを決定性単一テープTMによって多項式時間で判定できる言語のクラスとする。すなわち

  P = \cup_{k}TIME(n^k)

 

じゃあNPは非決定性単一テープTMで…？と思うかもしれませんが今回はそう定義しません。NPを定義するために、検証装置というものを定義します。

まず、検証とはどのようなものか例を交えて説明します。ハミルトン経路問題というものが存在します。これは有向グラフGとその節点s,tに対してグラフの全ての節点を一度だけ通ることを条件にsからtに向かう経路があるかどうかを判定するという問題です。単純にこの問題を解くとすると、指数時間アルゴリズムによる解法で挑むことになると思います。ハミルトン経路があるかどうか分からない状態では、sからtへの経路を全探索する必要があるからです。

一方、sからtに向かう経路が1つ与えられた時、その経路長をnとすれば、O(n)ステップでその経路をもとにそれがハミルトン経路であるか確かめる（検証する）ことができます。

以上のような考えのもと、多項式時間検証装置と呼ばれるものを定義します。

 

アルゴリズムVに対して言語Aを次のように定義できるとき、VをAの検証装置という。

A = {w| Vは、ある文字列cに対して<w,c>を受理}

 

検証装置の計算時間はwの長さについてのみ測ります。したがって、多項式時間検証装置とはwの長さに対して多項式時間でcの検証を行うアルゴリズムとなります。言語Aが多項式時間検証装置を持つとき、Aは多項式時間検証可能であると言います。

この多項式時間検証装置をもとにNPが定義されます。

 

NPは多項式時間検証装置を持つ言語のクラスである。

 

ただ、結局のところこれは次と同じことを言っています。

NPを非決定性TMによって多項式時間で判定できる言語のクラスとする。すなわち

NP = \cup_{k}NTIME(n^k)

 

さて、これでPとNPの定義が完了しました。分かりにくかったら申し訳ないのですが、少しでも頭が整理できたならば幸いです。

 

最後に、多項式時間還元のお話をします。これは問題AがPに属することを、Pに属する問題Bを利用して示すのに役立ちます。

多項式時間で計算可能な関数f : \Sigma^{*} → \Sigma^{*}を考え、言語AとBに対し、全ての w \in Aで以下の事柄が成り立つとします。

w \in A \leftrightarrow f(w) \in B

この時、 A \leq _{P}Bと書き、言語Aが言語Bに多項式時間還元可能であるといいます。では、以下の例題を解いてみようと思います。

 

Q. A \leq _{P}B, B \in Pならば A \in Pであることを示せ。

A. 示したい事柄は、Aを多項式時間で判定するアルゴリズムNが存在することである。 B \in Pより、Bを多項式時間で判定するアルゴリズムMが存在する。このとき、次のようにAを判定する多項式時間アルゴリズムNを構成する。

N = 「入力wに対して、

1. f(w)を計算する(多項式時間)

2. f(w)に対してMを動作させ(多項式時間)、その出力をそのまま出力する。」

\forall w \in A \leftrightarrow f(w) \in Bなので、Mが受理すればNも受理、Mが拒絶すればNも拒絶とすることでNはAを判定する。したがって、あとはNが多項式時間で作動することを示せばよいが、f(w)は精々wの長さに対する多項式程度の長さしかなく、それについて多項式時間のアルゴリズムMを動作させているのでNは多項式時間で動作する。したがってA \in Pである。

 

ではでは、マサカリが飛んでくるまでは一先ずこれで最後の編集とさせていただきます。皆さんテスト頑張ってください。

認識と決定（判定）の違い、決定可能言語の例

情報数学 数学

今回はチューリング機械の決定可能性に関する話です。

目次

 

受理・認識・決定（判定）

下図に示すようなことを説明していきます。（ C_1\in Q ではないです）

f:id:mkwamezaki1007:20190121200717j:plain

認識と決定の違い

計算状況についての記事で最後に触れたように、TM の状態には大きく分けて三つのものがあります。

  1. 受理状態
  2. 拒否状態
  3. ループ状態

この中では特に 3 番目のループ状態が異質に見えます。例えば DFA で考えると適当な入力を与えて遷移させれば、入力を使い切った段階で動作が停止します。つまり、入力となる各文字は使いきりです。したがって、入力が有限長である限りは必ず有限時間内に動作が停止します。一方で TM のヘッドは左右に動き、それゆえ与えられた入力に対して停止しないことがあり得ます（無限ループを起こすプログラムを書いたことがあると思いますが、そういった類の動作です）。

 

TM M の入力 w に対する受理・認識・判定について説明する前に、開始状況・受理状況・拒否状況について定義しておきます。

M=(Q, \Gamma, \Sigma, \delta, p_0, \sqcup, F) として、

  • 開始状況: (q_0, w, 1) と表される計算状況（ q_0\in Q は初期状態）
  • 受理状況: (q_{accept}, w', i') と表される計算状況（ q_{accept}\in Q は受理状態）
  • 拒否状況:  (q_{reject}, w', i') と表される計算状況（ q_{reject}\in Q は拒否状態）

これらの定義のもとで、 M が入力 w\in \Gamma^* を受理することを以下のように定めます。

  1. C_1 は入力 w に対する M の開始状況
  2. 各 i に対し C_i は C_{i+1} に移る
  3. C_k が受理状況
  • 1-3を満たすような計算状況 C_1\dots C_k が存在する時、 M は w を受理するという。入力に対する拒否も同様に定義する。

 

受理が定義できたところで、 M が言語 L\subset \Gamma^* を認識することについても定義します。

  • M が受理する入力の集合を L とするとき、 M は L を認識するという。

これらの定義から、以下の事実が分かります。

  • M が受理する入力の全体を L(M) （ M が認識する言語と呼ぶ）とすると、

　　　　 w\in L(M) \Rightarrow M は入力 w に対して必ず停止する

　 が成り立つ。

一方で、 w\notin L(M) についての言及はなく、拒否するかループするかは分かりません。もしこの場合の挙動が拒否に限定されていれば、いかなる入力に対しても計算が停止するという嬉しい性質が得られます。以上の考察を踏まえ、 M が言語を判定することを定義します。

  • M が認識する言語を L(M) とする。ある言語 L'\subset \Gamma^* に対し、 \forall w'\in L' に対して
  1. w'\in L(M) \Rightarrow M は w' を受理する
  2. w'\notin L(M) \Rightarrow M は w' を拒否する

　 が成り立つ時、 M は L' を判定するという。

 

この話の締めくくりとして、Turing 認識可能な言語と Turing 判定可能な言語を定義します。

  • 任意の言語について、その言語を認識するような Turing 機械が存在する時、その言語を Turing 認識可能と呼ぶ。
  • 任意の言語について、その言語を判定するような Turing 機械が存在する時、その言語を Turing 判定可能と呼ぶ。

 

決定可能（判定可能）言語

ここでは決定可能言語の例について述べていきます。

が、まだ準備中です（いかんせん全部やろうとすると量が…優先的に書いてほしいものがあればコメント等で教えてください）

 

 

計算状況とSATのNP完全性の証明における窓について(第11・12回スライド参照)

こんにちは。いつぞやに計算状況の記事を書きましたが、その定義を使って窓について考えると「んん・・・？」ってなります。私がなりました。そこで今回は、窓の書き方に合わせた計算状況を導入した後、合法な窓と非合法な窓について例示していきます。

 

 第2回スライドの説明記事で紹介した計算状況の定義では、現在の状態とテープ記号列およびヘッド位置の添え字を別々に記録していました。今回はそれをせず、状態およびヘッド位置をテープ記号列の中に組み込んでしまいます。例えばこんな感じに。

f:id:mkwamezaki1007:20190120171312j:plain

上図のように、現在の状態を示す記号の右側が現在のヘッドの位置となっています。

さて、これを基に窓について考えてみましょう。ある行とその下の行の関係は、現在の計算状況とその次の計算状況という関係です。したがって、下図に示す次動作関数に従ったTMを考えると、図のように合法窓と非合法窓が分けられます。

 

f:id:mkwamezaki1007:20190120165417j:plain

合法窓と非合法窓の例

 順番が前後し、かつ急ぎになりますが某競プロerの彼から質問を頂き緊急だと思いましたので何卒ご容赦ください。次回は決定性のお話をして、その後余裕があればPとNPについて書きます。