作成日: 2021/09/02 更新日: 2023/05/09 サイトの紹介と使い方
概要
複雑性理論と計算量理論
複雑性理論
複雑性理論の概要
- 基本的に計算可能関数を扱って、その関数の複雑性（解法の困難さなど）を研究します。
しかし、扱う問題に計算可能関数を適用できるか？分からない問題が多いのが現実です。 - 計算可能可能関数は、実効関数とも呼ばれ、現代のコンピュータで計算可能（実効性を持つ）な関数のことです。
- 創発もこの分野で研究されています。
子カテゴリ「創発」に創発の説明などの記事を記述します。
多項式の非線形関数
- 多項式の中に複数の非線形関数（変数の乗除など）が存在するケースです。
例えば、y=ab+cn+d!やy=abc+deなどです。
統計（単純回帰など）
- 回帰分析の中の単純回帰は、２つの独立するデータ（このデータをx,yとします）の関係度を計算する手法です。
- x,yに素因性がないと、通常の回帰分析は、確からしい計算ができません。
つまり、素因性がないと無関係の要素が入り込んで複雑というより、人為的な煩雑性が入り込みます。 - 観測や計測をするときに、何のデータを取得するのか？注意深く考える必要があります。
- 「複雑な問題だ！」と考えるとき、人為的な煩雑性が入り込りこんでいないか？データの素因性について考える必要があります。
複雑性理論が必要な問題
- 「自然界の事象を素因事象に分解できない」や「人為的な煩雑性が入り込りこんでいる」などのケースでも複雑性理論が必要とされます。
何故ならば、複雑性理論によって上述の問題が解決する可能性があるからです。
尚、人為的だから問題なのではなく、できるだけ人為性の意図性のある事象を排除しましょうという意味です。 - 創発は、複雑性理論が必要な代表的問題です。
「そもそも事象を起こす因子が特定できない」「事象が複雑に入り組んでいる（かもしれない）」「人為性の排除要因がわからない」など問題だらけで、何が複雑性で何が煩雑性なのかさえわかりません。 - 複雑性理論は、「因子（要因）が特定できない」「因子（要因）が入り組んでいる」などの問題を扱います。
計算量理論
- 計算可能性関数は、（現時点で）実効性を持たない関数のことです。
- 例えば、(19x19)！=10の765乗通りの組み合わせから、総当たりで最適な解を求めることは、現代のスーパーコンピュータでも不可能です。
おそらく、今の宇宙が何十回か滅んで、生まれ変わっても計算は終わらないだろうと言われています。 - (19x19)の数字は、一部の人達（あるいはもっとたくさん）で世界を驚かせたAI囲碁であるアルファ碁（現在は、アルファ碁は引退して、世界NO．1は絶影です）と比較したかったからです。
碁盤の目の数は、(19x19)です。
アルファ碁も絶影も第３次ブームの人工知能を使っています。
故に、確率的に人間より強いだけで、総当たりの100%の答えを持っていません。 - 昨今、話題のビッグデータは、現時点で計算可能な計算量のデータです。
対して、計算量理論は指数的な計算量を扱います。
ミレニアム懸賞問題-P‡NP予想-巡回セールスマン問題
- 2000年にアメリカのクレイ数学研究所が、100万ドルの懸賞金をかけた数学の未解決問題です。
- 7つの問題がありましたが、2020年10月末の時点で、1つ解かれたので６つになっています。
- その６つの中に「P‡NP予想」という問題があります。
- 巡回セールスマン問題は、P‡NP予想のNP困難に属します。
巡回セールスマン問題は、このカテゴリで扱います。
O記法（ランダウの記法）
- y = x3+x2 +xという関数があるとします。
この右辺で、xが増加した時、顕著にyの値に影響を与えるのは、x3です。 - これをO記法で表わすと、y = x3+x2 +x=O(x3)となります。
つまり、x3以外の項を無視するということです。
たかだか
- 計算量理論では、しばしば「たかだか」という語句を使用します。
- 例えば、O記法の他項の無視もこの「たかだか」の原則によります。
- また、定数も無視されます。
y=3x2=O(x2)となります。
メールアドレス：
