patternMinor
Assume that SAT ∈ PSIZE, does it imply that NP = coNP?
Viewed 0 times
assumesatimplyconppsizethatdoes
Problem
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 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 ?
Solution
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).
$\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).
Context
StackExchange Computer Science Q#23018, answer score: 3
Revisions (0)
No revisions yet.