Assume that SAT ∈ PSIZE, does it imply that NP = coNP?
-
31-10-2019 - |
Question
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 ?
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange