計算複雑性理論とは

サイトの紹介と使い方動画


created: 2021/09/02 modified: 2021/09/14

初めに

①最初に、煩雑と複雑の違いを、説明します。
②煩雑は、人為的な要素が含まれています。
つまり、その人為的な要素は人為的に取り除くことが可能です。
③複雑は、純粋なこの世界の自然的なもので、人為的な要素は含みません。

注意

①以下の記述には、筆者の解釈や主張が混じっています。
②そもそも、以下の理論は研究が大きく進んでおらず、社会貢献の段階まで行っていないと思います。
③筆者は学術的な理論は、主張による多数決ではなく、社会貢献ができる技術への転化として評価されるべきだと思っています。
④その前提で興味のある方は、以下の筆者の解釈や主張の混じった記述をご覧ください。

複雑性理論と計算量理論

①計算複雑性理論は次の複雑性理論と計算量理論の2つに大別されます。

複雑性理論

①基本的に計算可能関数を扱って、その関数の複雑性(解法の困難さなど)を研究します。
②計算可能可能関数は、実効関数とも呼ばれ、現代のコンピュータで計算可能(実効性を持つ)な関数のことです。
③ネット上で探しても、①と②以外に厳密な定義が見つかりませんでしたので、筆者の解釈や主張を記述します。
④次の2つのケースが考えられます。

入り組んだ非線形関数

①y=1/x は、反比例関数ですが、おそらくこれは、(複雑では無いので)複雑性理論の対象になりません。
②y=xz も①と同様です。但し、この関数が統計的、確率的に求められたものではないという条件付きです。
③y=x1x2x3...xnという関数を考えます。
また、y=xz を y=x1x2 と置き換えます。
下の関数の場合、x1とx2の関係性だけを考慮すれば済みますが、上の関数の場合、関係性はnの値が増えれば増えるほど、関係性は飛躍的に増えます。
④問題は、関数を解くことではなく、関数(あるいは方程式や法則)を組み立てる時に起こります。
⑤割り算が入ってくると、反比例と同じ作用が起こるのでさらに複雑になります。
⑥筆者は、複雑性理論の問題の1つが、これだと思っています。

確率的関数

①統計処理をするとき、1つの関数(方程式)を想定して、データ処理をしますが、この時必ず誤差が出ます。
②これは、データ処理に多くの場合、最小二乗法という手法を使っているからです。
③最小二乗法という手法に問題があるわけではなく、「算出された誤差の2乗の和を最小にするように方程式のパラメータを求める」という考え方が主流だからです。
④どのような手法を用いても必ず誤差は出ますが、最小二乗法が最も最適な解を求めることができるとされています。

計算量理論

①計算可能性関数は、(現時点では)実効性を持たない関数のことです。
②例えば、(19x19)!=10の380乗通りの組み合わせから、総当たりで最適な解を求めることは、現代のスーパーコンピュータでも不可能です。
おそらく、今の宇宙が何十回か滅んで、生まれ帰っても計算は終わらないだろうと言われています。
③(19x19)の数字は、一部の人達(あるいはもっとたくさん)で世界を驚かせたAI囲碁であるアルファ碁(現在は、アルファ碁は引退して、世界NO.1は絶影です)と比較したかったからです。
④囲碁は19x19のマス目で競われるボードゲームです。アルファ碁(絶影も)は、人工知能を使って作成されています。
⑤そして、世界NO.1囲碁棋士(囲碁のプロの人)に完勝しています。
⑥何故、宇宙が滅びる前に棋士(人)に勝てたかと言うと、確率的な解法を用いたからです。
⑦最善手(次の1手)を総当たりではなく、人工知能を使って確率的に求めたのです。
⑧「人工知能凄い」と思いますが、人工知能の目的にはまだ遠いのです。
興味のある方は、ディープラーニングの概要と全体像を参照してください。
⑨計算量理論と人工知能の理論の根底が違うので、一概に比較はできませんが、いつかこの2つが融合した時、本当に凄いことが起こるかもしれません。

ミレニアム懸賞問題

①2000年にアメリカのクレイ数学研究所が、100万ドルの懸賞金をかけた数学の未解決問題です。
②7つの問題がありましたが、2020年10月末の時点で、1つ解かれたので6つになっています。
③その6つの中に「P‡NP予想」という問題があります。
④計算量理論は、「P‡NP予想」とほぼ同じもの(似たもの)と言えます。
⑤「P‡NP予想」は、チューリングマシンを想定していますが、計算量理論の解法は大きく分けて2つあります(後述します)。

計算量理論

概要

①「前述した(19x19)!通りの組み合わせの中から、最適解を求めよ」と言う命題があったとき、現代の技術では世界中のコンピュータを繋げたとしても解くことは不可能です。
②あまりにも計算量が、大き過ぎるのです。
昨今、人工知能と一緒にビッグデータという言葉もよく聞きますが、計算量理論で扱う計算量は、ビッグデータが塵にも見えないほど、巨大なのです。
③「P‡NP予想」は、数百〜数千の数学的問題の総称のようなもので、その問題の1つでも解ければ、全ての問題が解けるのではないかと言われています。
④「P‡NP予想」は、NP完全とNP困難に分けられます(すみません、数年この問題から離れていたので現在は違う区分がされているかもしれませんし、年々この問題のネット上の解説が変わっています。世界中の皆さんが研究途中なので仕方ないのかもしれませんが)。
⑤巡回セールスマン問題はNP困難に属します。
⑥そして、計算量は、(Nー1)!/2になります。
Nは、都市数、つまり点数になります。

O記法(ランダウの記法)

①y = x^3+2x^2 +xという関数があるとします。

メールアドレス:

お問合せ・御要望

  • お問合せ
  • トップへ戻る
    タイトルとURLをコピーしました