素因数分解の他にも「一方通行」関数は存在します。数学の世界で「ナップサック問題」といわれる問題がそうです。
例えば
という数字があったとしますよね。これらの数字を組み合わせて（使わない数字があってもよい），『足し算するとちょうど 50 になるような組合せはあるでしょうか？』，『あるとするとそのような組合せは何パターンありますか？』という問題です。
この問題は数字がたかだか10個しかありませんから，しらみつぶしに調べればいずれ答えがあるかどうか，何パターンあるかということは分かるでしょう。しかし，一般的にこの問題はこれといった決定的な解法がなく，総当たりで調べるしか方法がありません。だから，数字が100個，1000個と多くなると途方もない時間がかかってしまいます。
これらの問題は数学で「P=NP問題」という問題と密接な関係があります。
昔，高校の頃『解の公式』を習いましたよね？。
の解は
というものでした。このように一般的な解法があるものはあらかじめ計算にどれくらいの時間がかかるのか見積もることが出来ます。これを「多項式時間(Ploymonial-time)で解ける」といいます。
これに対して「素因数分解」や「ナップサック問題」のような問題は決定的な解法が知られておらず，考えられるすべての場合をしらみつぶしに調べなければなりません。このような問題を「多項式時間で解けない(Nondeterministic Polynomial-time)」といいます。
でも，「素因数分解」や「ナップサック問題」は我々がうまい計算の方法を知らないだけで，ひょっとするとうまい方法があるのかも知れません。
そこで P 問題（Polynomial つまり多項式時間で解ける問題）と NP 問題（Nondeterministic Polynomial つまり多項式時間で解けない問題）については
前へ 次へ 