複雑性クラス
クラスP
クラスNP
NP完全
NP困難
クラスEXP
クラスP^PP
クラスP^#P
クラスBPP
https://ja.wikipedia.org/wiki/BPP_(計算複雑性理論)
乱択アルゴリズム
のクラス
クラスBQP
bounded-error quantum polynomial time
クラスP
を含むが、
クラスNP
は含まないと予想されているらしい
ref
https://ja.wikipedia.org/wiki/BQP
http://www.math.cm.is.nagoya-u.ac.jp/~hnishimura/kyudai_qclass.pdf
因数分解とか
クラスPSPACE
クラスMIP*
https://www.gizmodo.jp/2020/02/mip-re.html
#??
たとえ
量子コンピュータ
的なものが実現して、
NP完全問題
を
多項式時間
で解けちゃったらそれは
P=NP
ってことになるの？
ref
量子コンピュータ的なもので、「指数時間かかる問題」を「現実的な時間」で解けたとしたら、NPらへんの定義はどうなるの？
というか寧ろ「指数時間」という概念の意義が低くなる？
定義をそのままにしたら、NPの有用性が低くなりそう
mrsekut.icon
でも別にすべてのコンピュータが量子コンピュータになるわけではないから、有用性は下がらないか、しらんけど
https://ja.wikipedia.org/wiki/複雑性クラス
https://complexityzoo.net/Complexity_Zoo
死ぬほどある