計算理論からみた問題の分類を聞いてきた

８月６日

数学基礎論　サマースクール２０１７

の２日目午前前半（１日目の続き）を聞いてきた！ので、メモメモ

---

昨日のまとめ
　問題とは　入力された各文字列に対し答えが真か偽か定めたもの（のこととする）
　計算機構を厳密に定義　２つ→不可能性を示せた
　チューリング機械で解ける→機械的に溶ける
　　受理する：
　　認識する：真と偽で対称ではない
　　決定する：受理するときもしない時も停止する
　　決定可能：ＬもＬの補問題も認識可能
　　可能：チューリング機械が存在する
　→有限状態機械は、認識すると決定するが区別できなかった
　Ｕ：万能チューリング機械→対角線論法

・問題のむずかしさの比較：帰着
　ポストの揃え不可能性問題
　　（１）札は決まっていない
　　（２）一番初めのものはきまっている
　（２）が解ければ（１）はとける
　　　（１）は（２）に帰着される
　実は逆も言えるけど、難しい
　（１）が解ければ、（２）が解ける
　　上の段：文字のはじめに！　下の段：文字のおわりに！
　→そして、！（２）の１枚目にすれば、！ではじまるのは、それしかないので、
　　それしか使えない

　　　Ｕばー：認識不能
　　　　↓　帰着→これをこれからいいます！
　　　ポストの揃え(初手）：認識不能
　　　　↓　帰着
　　　ポストの揃え不可能：認識不能

・Ｕ：
　　　上の段：＃（開始状況）
　　　下の段：状況
　→上の段を、下の段の状況に合わせようとすると、下の段は自動的にうまる

・ヒルベルトの決定問題
　一階述語論理で書かれた主張が与えられたとき、それがこうしん（＝証明可能）
　か否かを決定する機械的な手順があるか
　　　解釈によるときは、いいえと答えてください
　　　どう解釈しても、存在するときは、はいと答えてください
　もしあるとすると、Ｕが決定可能になってしまうので、無い

おまけ
・計算量
　解析機関：Analytic engine チャールズ　バベジ

　同じ問題を解くにも複数の方法がある

・計算量の考え方
　１．チューリング機械の繊維の回数で図る
　２．入力文字数の長さに関する関数として表す（最悪時評価）
　３．その関数の増大の速さに着目
　　→増大の速さが、多項式以内かが重要

　多項式時間の機械で多項式問題をＰとする
　　→多項式以内か否かが重要：入力が大きくなると、手間が大違い
　　→指数個の組み合わせから何かを探す場面は多い（組み合わせ爆発）
　　　　素数、ハミルトン閉路
　　　　　→素数に関しては、ｎの多項式時間で解く方法が見つかった
　　　　　→ハミルトン閉路は見つかっていない
　問題■■は容易に解けるか＝効率の良い算法が存在する？

　可能とも不可能とも示せない重要な問題は多い

　多項式時間で解けない問題
　→多くの時間を使うと、より多くの問題が解ける：階層定理

　ＮＰ問題
　　多項式時間算法は見つかってはいないのだが
　　多項式時間算法が存在しないと証明されたわけでもない問題

・まとめ；問題の分類
　　認識可能
　　決定可能
　　ＥＸＰ
　　ＮＰ？
　　Ｐ
　　ＲＥＧ

・より詳しい入門書　「計算理論の基礎」


停止問題：決定可能でない
　決定可能→どれくらい決定可能でないかの段階がある
　→停止問題に帰着しない決定可能問題もある

多項式でも指数でもない、その間
　例２のlognの２乗

---

このあと、応用編だったのだが・・・
ごめん、よくわからなかったので、
メモは、控えておく・・・

市場予測の精度でも取引実績でも、AIは人間より優秀だ。

【タイトルの引用元】

ウォール街を襲うAIリストラの嵐
http://www.newsweekjapan.jp/stories/world/2017/08/ai-17_1.php

研究不正のバーチャル体験型の学習シミュレーション

The lab
http://lab.jst.go.jp/