概要 クラスPとは、決定性チューリングマシンにおいて、多項式時間で判定可能な問題のクラスであり、クラスNPは、Yesとなる証拠（Witnessという）が与えられたとき、多項式時間でWitnessの正当性の判定（これを検証という）が可能な問題のクラスである。多項式時間で判定可能な問題は、多項式時間で検証可能であるので、P⊆NPであることは明らかであるが、PがNPの真部分集合であるか否かについては明確ではない。証明はまだないが、多くの研究者はP≠NPだと信じている。そして、このクラスPとクラスNPが等しくないという予想を「P≠NP予想」という。 参考サイト : https://daigakudenki.com/np-hard/
数学の未解決問題 数学の未解決問題について説明します。問題自体はシンプルでも、証明されていない問題がまだまだたくさんあります。 完全数は無数にあるか？ 完全数とは、自分自身を除く正の約数の和が自分自身に等しい自然数です。 例えば、 6は約数は1,2,3となり、1+2+3=6なので完全数です。 28は約数は1,2,4,7,14となり、1+2+4+7+14=28なので完全数です。 現在51個しか発見されていませんが、無数にあると予想されていまが、 まだ、証明されていません。 ゴールドバッハの予想 ゴールドバッハの予想は、すべての2よりも大きな偶数は2つの素数の和として表すことができるという予想です。 （ここで素数とは、1と自分自身以外の約数を持たない自然数です。） 例えば、 4=2+2 6=3+3 8=3+5 10=3+7=5+5 問題自体は非常にシンプルですが、未だに証明されていません。 リーマン予想 リーマンゼータ関数の零点が、負の偶数と、実部が 1 / 2 の複素数に限られるという予想である。 リーマンゼータ関数は、$s$を複素数、$n$を自然数とするとき、 $$\zeta(s):=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}=1+{\frac {1}{2^{s}}}+{\frac {1}{3^{s}}}+{\frac {1}{4^{s}}}+\cdots$$ で定義される関数$\zeta$のことをいう。