P≠NP予想は計算量理論の話になります。 問題の集合(クラス)PとNPが等しくないという予想です。 「P」というのは,多項式時間で解ける問題のクラス,つまり「パソコンで解きやすい」問題です。 「NP」というのは,多項式時間で正解が本当に正しいか判定できる問題のクラスです。 もし,P=NPなら今まで解けなかったNPの問題が全て多項式時間で解けるようになってしまうので,そんな都合の良いことはないだろうという予想です。ちなみに,P=NPだと素因数分解の難しさを利用した現代の主要な暗号は破られてしまいます。 Pというのは,入力サイズに対して多項式時間で解ける問題のクラスです。 多項式時間かどうかというのは,四則演算や比較などのコンピュータ上での基本的な演算の回数で見積もります。 コンピュータを用いて指数時間かかってしまうような問題は現実的な時間で解くことができないのです。 例えば,n2n^2n2