＜集大成＞アルゴリズム大辞典
at TECH
266:デフォルトの名無しさん
07/02/14 18:10:31
>>265
NP=ある多項式長の補助入力が存在してPで解ける
総当り→補助入力は多項式長でないからダメ
補問題であるある場所にいけるかは
道順の例を補助入力として与えればこれは多項式長であり、明らかにPで検証可能。
したがって補問題はNP。
補問題がNPだから、PSPACEよりも狭いco-NPに入る。
次ページ続きを表示1を表示最新レス表示スレッドの検索類似スレ一覧話題のニュースおまかせリスト▼オプションを表示暇つぶし2ch
4390日前に更新/131 KB
担当:undef