# Assume that SAT ∈ PSIZE, does it imply that NP = coNP?

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 ?

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

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).