判定問題がPに属するなら探索問題はNPに属する。では判定問題がNPに属するとき探索問題は？

例えばある数が素数か？という素数判定問題はPに属することが知られていますが、この時、a以上b以下に素数が存在するか？という素数探索問題はNPに属すると言えます。
ではある判定問題がNPに属するとき、その探索問題はどのような計算クラスに属すると言えるでしょうか？

もうすこし具体的に言うとSATを解くための証明システムとしてpropagation redundancyというのがあるのですが、ある与えられたクローズCがpropagation redundancyで1ステップで導き出せるかどうか？というのがNP完全なんだそうです。
ではどのクローズがpropagation redundancy で 1ステップで導き出せるか？というpropagation redundancy クローズ探索問題はどのような計算クラスに属するのか？というのが知りたいです。

よろしくお願いします。

質問者からの補足コメント

• いわれてみるとpropagation redunancyクローズ探索問題がどのような問題か自分の中でもわからなくなってきましたorz.
  趣旨としてはpropagation redundancyであるクローズを探したい、なのですがこれだと判定問題になりませんね。。。

    補足日時：2023/05/20 20:00

• 

  CNF Fと自然数kが与えられたとして、長さk以下のクローズでFからpropagation redundancyで1ステップで導き出せるものが存在するか？ならどうでしょう？

    補足日時：2023/05/20 20:14

• なんかこれだと肝心のpropagation redundancy クローズが特定できない気がしますね。。。
  うーんどうしましょう？

    補足日時：2023/05/20 20:16

• CNF Fと自然数kと部分割り当てαが与えられたとして、長さk以下のクローズでかつαの拡張の部分割り当てをブロックするようなものがFからpropagation redundancyで1ステップで導き出せるか？ならどうですかね？。。。なんかまとまらなくてすいません。。。

    補足日時：2023/05/20 20:29

No.2 ベストアンサー 回答者： Tacosan 回答日時： 2023/05/21 01:17

「propagation redundancy」というものを知らずに書いているので申し訳ないと思いつつ一般論だけ.

「素数探索問題」のときに「NP に属する」といえるのは
・見付けるべき「素数」の「候補」を非決定性動作で作る
・その「候補」が素数かどうかを調べる
というように動かせばいいってだけだよね. ところが, 前者だけで非決定性多項式時間になっちゃうので, 後半の「素数かどうかを調べる」は P でも NP でも, 全体としては NP になる.

同じように考えると, 「propagation redundancy クローズ探索問題」では「候補」である「長さk以下のクローズ」が与えられる「CNF Fと自然数kと部分割り当てα」から (非決定性) 多項式時間で作り出せるかどうか, っていう勝負じゃないかな. 例えば k を入力で与えるときにはその「長さ」が O(log k) になる. つまり単純に「長さk以下のクローズ」を全部生み出すわけにはいかず, 工夫をしないといけない. もちろんあとで「ある与えられたクローズCがpropagation redundancyで1ステップで導き出せるかどうか？」を考えるので, その入力に合致させないとダメだ.

この回答へのお礼

回答ありがとうございます。
問題点が少し見えてきたような気がします。

お礼日時：2023/05/21 08:45

No.1 回答者： Tacosan 回答日時： 2023/05/20 19:41

「探索問題」がどのような「問題」なのかきちんと書いてくれないとわかりにくいんだがたぶん NP.