楚徨秤烏27
- 2. 凡}麻楚クラス ?麻楚クラスのイメ`ジ畜ではない 2 BPP NP complete NP P ? P(Polynomial problem) }が謹塀rgで盾ける ? BPP(Bounded-error Probabilistic P) }が_楕議に謹塀rgで盾ける ? NP(Nondeterministic P) }の基がYes,Noである嶄で }の基を謹塀rgで_Jできる ? NP complete NPの嶄で恷もyしい ? NP hard もっともyしい}で、 基がYes,Noでないものも根む NP hard
- 3. 6.7 ブラックボックスアルゴリズムの渊 3 ?Y ?吭龍 楚徨アルゴリズムは硬灸アルゴリズムより謹塀 參貧の互堀晒はできない。 ?催の吭龍 ? ?FD ? ?FQ2 楚徨コンピュ`タが、}Fを_楕議に盾くのに オラクルを柵び竃さなければならない指方 硬灸コンピュ`タが、}Fを盾くのに オラクルを柵び竃さなければならない指方 ? ? ? ? ? ? 6/1 6 2 ~ 13824 FD FD FQ ?
- 4. 6.7 ブラックボックスアルゴリズムの渊 ?箭坤哀踪`バ`のアルゴリズム グロ`バ`の楚徨冥沫アルゴリズムはこのYを 困燭靴討い ?^苧 ＾謹塀の圭隈￣を喘いて幣すことができる 4 ? ? ? ? ? ? ? ? 6/1 62 2 ~ 13824 FD FD FDFQ ?? 歌深http://www.cs.cmu.edu/~odonnell/quantum15/lecture11.pdf