英大学、量子コンピュータを超える「非決定性万能チューリングマシン」の実現可能性を指摘(1/1)

計算のサイズ(n)に対し、nの多項式時間を必要とする判定問題はP問題と呼ばれる。指数関数時間などになると、計算のサイズに対し計算量は莫大な増加をする。