3
$\begingroup$

Assume that $\mathrm{SAT} \in \mathrm{PSIZE}$, does it imply that $\mathrm{NP} = \mathrm{coNP}$ ?

I think that I've managed to show that if $\mathrm{SAT} \in \mathrm{PSIZE}$, then both $\mathrm{NP}$ and $\mathrm{coNP}$ are contained in $\mathrm{PSIZE}$, but I can't see how does help me. Any ideas ?

$\endgroup$
  • $\begingroup$ I wonder whether space-complexity would be more appropriate here. $\endgroup$ – Raphael Mar 24 '14 at 22:44
  • $\begingroup$ Space complexity is something different. This is circuit complexity or non-uniform complexity. $\endgroup$ – Yuval Filmus Mar 25 '14 at 1:22
  • $\begingroup$ could someone define or ref PSIZE? afaik this is not a real complexity class. $\endgroup$ – vzn Mar 25 '14 at 20:24
  • $\begingroup$ @vzn: $L\in P/poly$ if and only if $L$ has polynomial circuit complexity ($L \in PSIZE$) $\endgroup$ – Vor Mar 25 '14 at 20:47
  • $\begingroup$ @Vor ok was guessing that. do you know of a std ref pref book (paper ok if not) that uses it? $\endgroup$ – vzn Mar 25 '14 at 20:51
3
$\begingroup$

If $SAT \in PSIZE$ then the polynomial hierarchy collapses to the second level: $\Sigma_2 = \Pi_2$ (see Karp-Lipton theorem ); but $NP=coNP$ (i.e. $\Sigma_1 = \Pi_1$) is stronger (the PH collapses to the first level).

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.