NP完全の話は、おそらくあまりピンとこないと思いますので、もう少し分かりやすく説明できるか挑戦してみたいと思います。
LSIの中でも論理LSIはメモリーと異なり、設計の段階で複数のトランジスターから構成される論理セル（ANDやOR等の基本ブロック）を、如何に平面的なシリコンウェハー上に配置し、如何に相互間を配線するかが重要です。
配線が長くなると信号遅延が増大するため、動作周波数（クロック速度）に制限を与えてしまいます。できるだけ配線長を短くするためには、まず論理セルの配置が適切に行われていなければなりません。
各論理セルには、それぞれ信号の入力と出力の為の端子があり、たとえば3入力のANDの場合は、3つの入力端子と1つの出力端子があります。
出力信号は、ほとんどの場合同時に複数の論理セルに接続され、多い物では100以上もの論理セルと接続されます。これらの論理セルを、すべての接続を最短にするように配置する事は、容易ではありません。
分かりやすくなるかどうか分かりませんが、別の例で考えてみましょう。
今、40人の生徒がいるクラスの席替えをしようとしています。できるだけ生徒全員が満足する席の配置を目指します。
仲が良い3人の友達と一緒になりたいという生徒がいたり、5人と仲がよい生徒がいたり、クラス全員の人気者がいたり、いろいろな条件がありそうです。
さらに、勉強したいから一番前で先生の話がよく聞こえる席が良いという生徒がいたり、先生から目が届かない席に行きたがる生徒がいたり、憧れの異性の側に行きたがる生徒がいたり、それぞれ異なった要求が出てきます。
問題は、ある一人の生徒を満足させるだけなら簡単なのですが、それが他の生徒を満足させるとは限らないと言うことです。LSIの場合は、生徒が数百万人いる教室の席替えをするようなものですから、あまり関わりたいとは思いませんね。
まだ問題の難しさがよくわからんとおっしゃる方がおられたら、こんな例は如何でしょうか？
家系図は、先祖から子孫への系譜を示す物ですから、だんだんと末広がりにわかりやすいように書いていますが、実際は先祖にたどっていく方向にも広がって行くわけです。
つまりすべての親から子、子から親の関係を図示し、数百万人分の系図を一枚の紙に書くのと同じ作業だと言えば、そう簡単ではないのが分かるのではないでしょうか。
話をLSIに戻します。ある一つの論理セルAの出力が、別の論理セルB、C、Dの入力に接続されており、論理セルBの出力は、別の論理セルE、F、Gの入力に接続されている。これを数百万個のセルに対して繰り返すのです。
初めから決まったルールや解法がないので、乱数を発生させながらヒューリスティックな方法で最適解を探して行きます。このような方法を、一般にギャンブルに例え、モンテカルロ法と呼んでいます。
さて、問題の複雑さを理解していただけたでしょうか？何かごちゃごちゃしていると感じて頂ければ十分です。
次回は、モンテカルロ法についてです。