英大学、量子コンピュータを超える「非決定性万能チューリングマシン」の実現可能性を指摘 ～DNAを用いたコンピューティング理論 - PC Watch

2017/03/02 308 users 量子コンピュータ 論文 DNA 過程 実現可能性

計算のサイズ(n)に対し、nの多項式時間を必要とする判定問題はP問題と呼ばれる。指数関数時間などになると、計算のサイズに対し計算量は莫大な増加をする。 　英マンチェスター大学は1日(現地時間)、DNAの複製メカニズムを利用し、同時に異なる全ての過程を並行してシミュレーションできるDNAコンピュータの実現可能性を発表した。これについて、同学のRoss D. King教授による論文が英Journal ... 続きを読む