計算量とグラフ

P≠NP予想

P≠NP予想は、計算複雑性理論（計算量理論）におけるクラスPとクラスNPが等しくないという予想です。

・クラスP：多項式時間（polynomial time）で解ける判定問題の集合
・クラスNP：非決定性チューリングマシンによって多項式時間で解くことができる問題の集合
これを簡単にいうと、入力ｘと出力ｙがあったとき、
・クラスＰ：ｙ＝ａｘのように入力ｘと出力ｙが比例する（あるいはそれに近い）問題
・クラスＮＰ：ｙ＝ａのｘ乗のように入力ｘの増加に伴い出力ｙがとんでもなく増加していく問題

となります。

巡回セールスマン問題

巡回セールスマン問題は、P≠NP予想の中でＮＰ困難と呼ばれ最大級の問題とされています。
どのくらい困難なのかというと、入力Ｎがあったとき、

（出力）ｙ＝Ｎ！（階乗）

となるくらいです。

グラフ

さて、以下に図１～図３のグラフを用意しました。
横軸は入力ｘ、縦軸は 出力ｙとなります。

図－１

　図１は指数関数のグラフで、ｘが増加するとｙは急こう配を持った曲線となって増加していきます。

図－２

　図２は比例関数のグラフで、ｘが増加してもｙも比例定数のこう配に従った増加となります。

図－３

図３は対数関数のグラフですが、これについては後述したいと思います。

　図１はクラスＮＰに属し、図２はクラスＰに属すると考えても概念的には問題ないと思います。

対数グラフ

図３の対数関数のグラフは、ｘが増加してもｙの増加率は減少していきます。
計算複雑性理論（計算量理論）の目的からいくとこの対数関数は比例関数より優れていると思います。

この対数関数を用いたアルゴリズムはツリー構造として、現代のソフト（プログラム）に広く使われていますが、扱うものによっては、アルゴリズムが構築できません。

例えば、ｙ＝Ｎ！をどのようにして対数関数に展開するのかと考えると、未だ人類はそこに到達していません。
本ブログの目的は、この対数関数に展開するアルゴリズムを完成させることにあります。

７年ほど前に構築したアルゴリズムは、完成形の２０％～３０％くらいと気づき、完成形１００％に近づくように本ブログを立ち上げました。

そのアルゴリズムの方向性は正しく、ただ足りないものが多すぎるのだと信じて本ブログ（またはホームページ）を積み上げていきたいと思っています。