はじめに

P=NP?問題について、専門的な話は追々説明していくことにして、私なりに分かりやすく説明すれば、こういうことになるかと思います。

あなたが、7時からラジオでニュースを聞こうと思ったとします。そうすると、大概の人はその内容を理解できますよね。ごく当たり前のことです。

ところで、あなたが寝ているとします。何か音が聞こえた。それが「火事だ」という声だとします。どうしてあなたは、たくさんの音の中から「火事だ」という声を拾ってその内容を理解できたのでしょう？そして、これは、普通私たちがラジオのニュースを聞こうと思って、聞いて理解することとと同じなのでしょうか？

まとめると、ラジオニュースを理解する、という問題がP=NPのPに相当する問題です。寝ているときに突然「火事だ」という声を理解するという問題がNPに相当すると考えてください。

PとかNPということばを理解するには、少しだけ、集合論を理解する必要もあります。これは、追々説明します。

ただ、まず、われわれは、上のような例のPとNPが同等の問題かどうか、すなわちP=NP？か、ということを数学的に解こうとすると実は大変なことなんだ、ということをここでは知っておけば良いと思います。