私は$ 2 ^ n $ビットサイズの証明書に関する決定問題を持っています、それが$ NP $であれば私の決定問題を効率的に検証するのでしょうか。

Question

決定問題： $ 2 ^ k $ + $ m $ Prime？

$ k $ 、 $ m $ の両方の入力は整数です。解決策は、 $ 2 ^ k $ + $ m $ の合計です。 （ Prime を決定するためにAKSを使用）

2の力は、約 $ 2 ^ n $ 数字を持ちます。 $ 2 ^ k $ を考慮して、 $ k $ = 100000. $ k $ ソリューションの桁数へ！

質問

決定問題の証明書が $ 2 ^ n $ サイズであることを確認して、私は多項式の時刻の決定問題をどのように検証するのでしょうか。それ自体の証明書としての遷移状態？

言い換えれば、多項式の時間検証者はこの決定問題のように見えるものは何ですか？

Answer 1

決定問題はyes / no答えを持っているので、「指数関数的サイズ」を持つことはできません。検索の問題について尋ねている、それらは確かに指数関数的サイズを持つことができます。はい、解決策のサイズ（すなわち、一部の適切なコンパクト形式で書き留めて、すなわち一部の適切なコンパクトな形式で書き留め）が元の問題のサイズで指数関数的である場合、それは多項式時刻で答えを書き留めることさえできません。

いずれにせよ、PとNPは決定問題にのみ適用されます。しかし、Belareの "Decision Vs検索" 両方の関係。