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$
8
  • $\begingroup$ I wonder whether space-complexity would be more appropriate here. $\endgroup$
    – Raphael
    Mar 24, 2014 at 22:44
  • $\begingroup$ Space complexity is something different. This is circuit complexity or non-uniform complexity. $\endgroup$ Mar 25, 2014 at 1:22
  • $\begingroup$ could someone define or ref PSIZE? afaik this is not a real complexity class. $\endgroup$
    – vzn
    Mar 25, 2014 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, 2014 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, 2014 at 20:51

1 Answer 1

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.