断っておくが、一般に言うP≠NP問題とは違う話である(面白い切り口にはなるかもしれないが)。
チューリングマシンの計算オーダーで、多項式時間で解けない問題は多数あるが、これを非チューリングマシンでPの計算オーダーで解く事は可能である。
たとえば量子コンピュータがそうであるし、当のチューリング自身がチューリングボンベでエニグマを解読する際に非チューリングマシンの可能性は示している。
チューリングマシン自体は「計算する」ということの範疇を定義するためのモデルでありそれ以上でも以下でもない。
たとえば素因数分解は多項式時間では解けない。
ここで、件のNAND恒等回路で乗算器を組むことを考える。
A*B=C の回路において、まずCの部分の各端子を+1 or -1 で固定します（ここでテンション掛けてもその値に出来なければそれは素数）。
この段階でこの回路は、乗算結果がそうなる値の集合の範疇でしか遷移不能になる。
先の記事で示したとおり、各解の集合間での遷移はスムーズに進行する。
Nbit桁の乗算の場合、O(N)のオーダーで一つ目の解の探索が完了する。
量子コンピュータに比べて対応する記憶素子が無いなどのデメリットもあるが、この回路は現在のCMOSプロセスで容易に構成可能である点はメリットであるであろう。
P≠NPの仮定の基、各種の暗号の安全性も担保されているわけだが、まあ世の中には既にどこかにこの手の装置は実用化されていそうな気がする。
コメント