乱択アルゴリズムのクラス

クラスPを含むが、クラスNPは含まないと予想されているらしい ref

因数分解とか

#??

たとえ量子コンピュータ的なものが実現して、NP完全問題を多項式時間で解けちゃったらそれは P=NP ってことになるの？ ref

量子コンピュータ的なもので、「指数時間かかる問題」を「現実的な時間」で解けたとしたら、NPらへんの定義はどうなるの？

というか寧ろ「指数時間」という概念の意義が低くなる？

定義をそのままにしたら、NPの有用性が低くなりそう

でも別にすべてのコンピュータが量子コンピュータになるわけではないから、有用性は下がらないか、しらんけど

死ぬほどある