在NP $ cap $ co-np中可以解决问题的问题

Question

令$ mathcal {a} $成为$ text {np} cap text {co} $ - $ text {np} $中的问题。

现在假设我们可以使用cook降低将另一个问题$ mathcal {b} $减少。

我们可以得出关于$ Mathcal {B} $的哪些结论？这个问题甚至有意义吗？

我之所以问，是因为我从我理解的内容中缩减与karp降低不同（例如，$ text {np} $无法与$ text {co} $ - $ text {np} $区分开。我很困惑，似乎无法真正理解库克减少的特性。关于该主题的任何良好参考也将不胜感激！

我希望这个问题不是太基础了，但是我找不到任何问题。

Answer 1

好的问题/作业！

以另一种方式说明：$ mathsf {np} $在cook降低下未关闭（假设$ mathsf {p} neq mathsf {np} $）。

$ mathsf {np} cap mathsf {conp} $怎么样？ $ mathsf {np} cap mathsf {conp} $在库克还原下关闭吗？是$ mathsf {np} $在库克降低下未关闭的唯一原因是因为它没有在补充下关闭，因此，如果我们服用这些$ mathsf {np} $问题，其补充也为$ mathsf {np} $我们解决问题吗？

例如，如果我们将库克从问题减少到保理，这是否意味着问题是在$ mathsf {np} cap mathsf {conp} $中？

Oracle不仅允许我们询问Oracle中的会员资格和非会员资格，还使我们能够询问非常复杂的问题列表，每个问题都可以取决于上一个问题的答案。

让我们看一个问题$ q in mathsf {p^{np cap conp}} $。我们知道有一个多项式时算法$ m $和set $ a in mathsf {np cap conp} $，因此$ m^a $解决了问题$ q $。 $ q $是$ mthsf {np} $吗？

提示：$ m^a $什么时候接受输入$ x $？

如果这是一项作业，请不要阅读下面的答案，答案并不困难，如果您花了几个小时在上面，您应该能够解决它，而花这些小时才能使您学习。

让我们看一下输入$ x $上的$ m^a $的执行。 $ m $在计算过程中将对$ a $进行许多查询，并会收到是和否答案，最后会接受或拒绝。如果我们可以在多项式时间内计算回答查询的答案，我们将证明问题是在$ mathsf {p} $中，我们将模拟算法$ m $，并且只要从$ a $ a $询问查询时，我们就会计算答案并给出$ m $，并继续进行模拟。

但是$ a in mathsf {np cap conp} $，我们不知道如何在多项式时间计算查询的答案。但是我们不需要在多项式时间内执行此操作！我们可以猜测问题的答案，并在多项式时间内验证我们的猜测。为了能够验证正面和负面答案的答案，我们需要在 mathsf {np cap conp} $中$ a a ，这就是为什么这不适合$ a in in mathsf {np} $不起作用的原因，这将是为什么仅允许验证积极的答案。

令$ v_ {yes} $和$ v^{no} $为两个多项式时间验证符，用于会员资格和$ a $中的非会员。考虑使用如下的verfier $ v（x，y）$：

I.检查$ y $由1组成1.一个字符串$ c $（$ x $上的$ m $计算），2。字符串列表$ q_1， ldots，q_m $（查询$ c中的oracle $），3。字符串$ a_1， ldots，q_m $（来自Oracle的查询的答案），4。字符串列表$ W_1， ldots，w_m $（证书/证明/证人/证人的正确性查询答案）。
ii。查看查询列表$ q_1， ldots，q_m $包含$ c $中的所有oracle查询，
iii。如果查询的答案为$ a_1， ldots，a_m $，请检查计算$ c $在$ x $上接受$ m $的接受计算。
iv。对于所有$ 1 leq i leq m $，请检查如果$ a_i = yes $ the $ v^{yes} $接受$（q_i，w_i）$，以及$ a_i = no $ $ $ the $ v^{no} $接受$（q_i，w_i）$。

所有这些步骤都可以在多项式时间内检查。因此，我们有一个验证器，可用于$ m^a $的Yes Answers。此外，请注意，如果$ m^a $接受$ x $，那么满足具有多项式大小的这些条件的$ y $：多项式计算机的计算是多项式大小的，查询数量和大小在输入中，所有查询也是多项式。此外，查询证书的大小也受查询大小的多项式界定，因此在输入的大小中再次是多项式。简而言之，我们有一个带有$ m^$的多项式大小证书的多项式验证器。
这完成了证明$ q in mathsf {np} $。一个类似的参数表明$ q in mathsf {conp} $。因此，$ q in mathsf {np cap conp} $。换句话说，$ mathsf {p^{np cap conp}}} subseteq mathsf {np cap conp} $。

Answer 2

如果$ mathcal {a} in mathrm {np} cap mathrm {co text { - } np} $，则有$ x in mathcal {a} $的证人以及$ x notin mathcal {a} $。换句话说，如果我给您一个带有Oracle的计算以访问$ Mathcal {a} $，我可以说服我没有通过提供适当的证人来对Oracle答案撒谎。

由于$ MATHCAL {B} $ COCK-REDUC将$ Mathcal {a} $重新换成，因此您可以在多项式时间内使用Oracle到$ Mathcal {a} $在多项式时间内解决$ Mathcal {B} $。连接点，我们得出结论，$ mathcal {b} in mathrm {np} cap mathrm {co text { - } np} $。