PSPACE困難とNP困難について

全てのNP困難な言語がPSPACE困難でもあるならばPSPACE=NPとなることの証明を教えてください。

NP⊆PSPACEが成り立ち、NP困難とPSPACE困難が等しい時にPSPACE=NPとなるのはなんとなくわかるのですが、具体的な証明が分かりません。

No.4 回答者： Tacosan 回答日時： 2015/10/31 23:57

あ,

https://oshiete.goo.ne.jp/qa/9099051.html
の方は処理しといてね.

No.3 回答者： Tacosan 回答日時： 2015/10/31 00:15

「NP困難の部分とPSPACE困難が等しい」とはどういうことですか? 「その範囲が同じ」の「その範囲」とは具体的にはなんの範囲なんですか?

まずは NP困難や PSPACE困難の定義を書いてみよう. そして, 「全てのNP困難な言語がPSPACE困難でもある」ということから何が言えるか書き出してみよう. さらに, 「何が示せれば『PSPACE = NP』と言えるのか」もきちんとした日本語で表現してみよう.

あとは, #1 に書いたように NP完全がキーになるはずだから NP困難と NP完全の関係がわかっていれば途中を埋めるだけの作業.

この回答へのお礼

分かりました。
ご丁寧にありがとうございます。
挑戦してみます。

お礼日時：2015/10/31 14:22

No.2 回答者： Tacosan 回答日時： 2015/10/30 16:49

あなたがどこまでやってどこで困っているのかを見せてください.

この回答へのお礼

イメージとしてNP困難の部分とPSPACE困難が等しくて、その範囲が同じなため成り立つということだと思うのですが証明がの取っつき方が分からず困っています。
よろしければ教えてください

お礼日時：2015/10/31 00:04

No.1 回答者： Tacosan 回答日時： 2015/10/30 14:19

NP完全=PSPACE完全

になるから, ってところかな.

この回答へのお礼

ありがとうございます。
よろしければ具体的な証明も示してもらえないでしょうか？

お礼日時：2015/10/30 16:25