If $NP\subseteq P/log\implies P=NP$ why does $coNP\subseteq NP/O(1)$ or $coNP\subseteq NP/O(\log n)$ not implies $coNP=NP$?

  • $\begingroup$ If NP is low for itself then ​ NP = coNP . ​ ​ ​ ​ $\endgroup$ – user12859 May 5 '16 at 6:04
  • $\begingroup$ yes thank you but that is not the problem here. $\endgroup$ – T.... May 5 '16 at 6:08
  • $\begingroup$ In that case, I'm quite curious what the problem here is. ​ ​ $\endgroup$ – user12859 May 5 '16 at 6:09
  • 1
    $\begingroup$ Here, the weird thing is that $\mathrm{NP\subseteq P/log\to P=NP}$ holds, not that the other implication does not. It relies on self-reducibility: if $\mathrm{NP\subseteq P/log}$, the $\log$-size advice can be used to find a satisfying assignment to any given satisfiable formula. Now, we don’t know which advice string is correct, but there are only polynomially many possible choices. We can try them all, and we can recognize a correctly computed satisfying assignment. There is no analogue of this in the $\mathrm{NP\subseteq coNP}/O(1)$ situation. $\endgroup$ – Emil Jeřábek May 5 '16 at 18:11
  • 1
    $\begingroup$ @EmilJeřábek : ​ ​ ​ The reason for there being "no analogue of this in the" coNP situation, is that coNP is not known to be low for itself. ​ If P can perform the self-reduction, than coNP can also do so. ​ While self-reducibility is important for the conclusion, it's not the difference between the two situations. ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user12859 May 5 '16 at 23:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.