量子コンより速い計算機
1.数学の世界では、NP問題の中に「NP完全」と呼ばれる特別な問題がある。すべてのNP問題は、現実的な時間内での計算によってNP完全問題の形に置き換えられることがわかっているので、もしもNP完全問題を現実的な時間内に解くことができれば、すべてのNP問題が解けることになる。
2.通常コンで現実的な時間内に解くことができる問題は「クラスP」の問題と呼ばれる。実際にNP完全問題を現実的な時間内に解くアルゴリズムが存在するならば「P=NP」であることになる。逆に、そのようなアルゴリズムが原理的に存在しないならば「P≠NP」になるが、どちらが正しいのかについてはいまだ証明されていない。これが「P=NP予想」または「P≠NP予想」と呼ばれる数学上の未解決問題である(「P≠NP予想」は100万ドルの賞金がかかったミレニアム問題の1つでもある)。
3.NP完全問題については、量子コンを使ってもやはり現実的な時間内に解くことはできないのではないか、という予想がある。一方、NUTMが実現されれば、NP完全問題も高速のしらみつぶしで解けてしまうと考えられる。つまり、NUTMが実現すると「P=NP」であることが証明される可能性がある。
4.しかし、「P=NP予想」が正しく、従って全てのNP問題が解かれてしまうという事態は、ありそうにないと考えられるため、専門家のあいだでは「P≠NP予想」を支持する人のほうが多い。どちらが正しいのかは未解明の問題であるが、仮に「P≠NP」であるなら、NUTMは実際には作れないのではないか、とも考えられる。
5.NUTM「非決定性万能チューリングマシン( non-deterministic universal Turing machine)」