1.数学の世界では、NP問題の中に「NP完全」と呼ばれる特別な問題がある。すべてのNP問題は、現実的な時間内での計算によってNP完全問題の形に置き換えられることがわかっているので、もしもNP完全問題を現実的な時間内に解くことができれば、すべてのNP問題が解けることになる。
2.通常の計算機で現実的な時間内に解くことができる問題は「クラスP」の問題だ。NP完全問題を現実的な時間内に解くアルゴリズムが存在するならば「P=NP」となる。存在しないならば「P≠NP」になる。「P=NP予想」または「P≠NP予想」という未解決問題で百万ドルの賞金がかかった問題の1つだ。
3.NP完全問題については、量子計算機を使っても現実的な時間内に解くことはできないのではないか、という予想がある。一方、NUTMが実現されれば、NP完全問題も高速のしらみつぶしで解けてしまうと考えられる。つまり、NUTMが実現すると「P=NP」であることが証明される可能性が高くなる。
4.しかし、「P=NP予想」が正しく、従って全てのNP問題が解かれてしまうという事態は、ありそうにないと考えられるため、専門家のあいだでは「P≠NP予想」を支持する人のほうが多い。どちらが正しいのかは未解明の問題だが、仮に「P≠NP」であるなら、NUTMは実際には作れないとも考えられる。
5.NUTM「非決定性万能チューリングマシン( non-deterministic universal Turing machine)」DNAを利用する超高速で並列処理計算を行う新型コンピュータが実際に作製可能であるとする研究が発表された。量子コンピュータでも現実的な時間内に解くことができない難問も短時間で解くことができると主張。
6.計算に使える時間に限りがあるように、計算に使える空間にも限りがある。地球上の原子の数がおよそ10の49乗個、宇宙全体の原子の数がおよそ10の80乗個、計算に必要なDNA分子数が指数関数的に増大していく場合、やはり現実的には解けない問題があることは明らかだ。
7.DNA分子を用いてコンピュータを微小化することによって空間を有効利用すれば既存の最高性能スパコンを凌駕するNUTMは実現できる。DNAコンピュータで毎秒10の20乗回の計算が可能、実行可能な計算回数が2×10の19乗回という低消費エネルギーが実現できる。
http://hexus.net/tech/news/cpu/103207-nutm-computer-uses-dna-processors-can-self-replicate/
8.IBMの量子計算機を使う。IBM は、2016年5月4日に世界で初めて、量子コンピューターをクラウドで公開
https://www.ibm.com/developerworks/jp/cloud/library/cl-quantum-computing/index.html