はじめに
どんなに高性能なパソコンでも解ける問題と解けない問題があります。
また、解けるけど解くのに数十年もかかるような問題も現実的ではありませんよね。
今回は計算論の基本的なこと(PとNP)を勉強したので以下にまとめます。
数学の世界に関して
数学では、
3 とか -2 とか -0.05 とか √5 とか
様々な数値を使って答えを導きます。
また、全ての数値は
自然数、整数、有理数、実数、複素数
の5つの集合のどれかに必ず含まれています。
下記のようなイメージです。
N ∈ Z ∈ Q ∈ R ∈ C
と表すことが出来ます。
N: 自然数
Z: 整数
Q: 有理数
R: 実数
C: 複素数
つまり、
全ての数字は、
複素数に含まれており、
その中で色々と式が組み合わされているわけです。
自然数
1以上の値
例) 1, 2, 3, 4
整数
0、負の数、正の数
例) -2, -1, 0, 1, 2
有理数
分数で表せる数
例) -1, -0.02, 0, 0.5, 10, 3/5
※整数/整数で表せる数が有理数なのですが、
分母が0の場合は存在しないので有理数に含まれません。
分子が0の場合は有理数に含まれます。
実数
有理数と無理数(分数で表せない数)を合わせた数
無理数の例) √2, √3, π, e
複素数
実数a,bと虚数単位iを用いてa+biと表せる数
例)
x^2+2=0を解くとx=±√-2となる
このときルートの中のマイナスをiに置き換え、
x=±√2iと表すことができる。
無限についての理解
皆さんは無限という言葉を数学などで一度は聞いたことがあると思います。
無限といったら数えられないとかたくさんとか...表現はたくさんあると思います。
しかし、
無限の中にもレベルがあります。
(ドラゴンボールのスーパーサイヤ人...金髪に変身するといってもスーパーサイヤ人2や3がありますよね。それと似ています。）←わかりづらかったらスミマセン(汗)
詳しくは↓
無限を最短で紹介するよ
ズバリ言うと、
無限の中には、
可算無限と非可算無限の2種類が存在しています。
可算無限とは
自然数と1対1対応できる無限です。
要するに、
いつかは答えが見つかる数です。
アレフゼロといいます。
自然数、整数、有理数が含まれます。
非可算無限とは
自然数と1対1対応出来ない無限です。
要するに、
√2のように数えても答えにたどり着かない数です。
アレフ(記号：א)といいます。
実数と複素数が含まれます。
P, NP, NP完全, NP困難, 対角線言語について
P∈NPであるといえます。
問題には、
コンピュータを使用しても解ける問題と解けない問題があります。
詳しくは下記のサイトを参考にして下さい。
意外と知らない、【階乗】の恐ろしさ
つまり、
2^nのように指数がnとされている場合の計算はヤバイってことです。
コンピュータの天敵です！
もっと詳しくいいますと、
指数の部分が√2のような無理数であると計算するのに一生を費やしてしまうぐらいかかってしまいます。
このような問題をNPといいます。
クラスPとは
多項式時間
多項式時間アルゴリズム
つまり、
現実的な時間で解を求めることができます。
クラスNPとは
非決定性多項式時間
指数関数時間アルゴリズム
つまり、
解けるけど、現実的な時間で解を求めることができません。
134^1000000000の答えを出せというような問題
NP完全とは
NPの中で最も難しい問題
10^√2の答えを出せというような問題
NP困難とは
NP完全と同等以上に難しい問題
NPでない問題も含まれている
対角線言語
対角線言語とは、いかなるチューリングマシンによっても受理されません。
つまり、決して解けない問題です。
以下に、どのような値が対角線言語であるか説明します。
上記の画像を参考に。
画像の帰納的可能言語(帰納的可算問題)とは、
おおざっぱに言うと、
解ける問題をそう定義しているだけです。
(チューリングマシンが受理できれば解けたといえます。)
まず帰納的可算言語(0と1で表した値)をいくつか並べます。
次にその値をビット反転します。
そして、ビット反転した値の対角線の数字を取って並べた値(画像の場合は10011)が対角線言語です。
この対角線言語は絶対に帰納的可能言語の値と一致しません。
まとめ
・無限には可算無限と非可算無限がある。
・自然数∈整数∈有理数∈実数∈複素数であり、無限の中で自然数の無限が一番小さい。
・クラスPとは時間はかかるけど解ける問題のことである。
・クラスNPとは解けるけどとてつもなく時間がかかるため現実的ではない問題のことである。
・対角線言語とはチューリングマシンで絶対に受理されない。
おまけ
テイラー展開とマクローリング展開
解説動画
https://www.youtube.com/watch?v=3AbiJ8cMVtU&feature=youtu.be
おわりに
色々なサイトを見て自分なりにまとめてみました。
数学の専門家でないため、
まとめ方におかしな部分があればご指摘お願いします。