gotchaMinor
Why does coNP⊆NP∖P imply that the polynomial hierarchy collapses?
Viewed 0 times
conpwhyimplythecollapsespolynomialhierarchythatdoes
Problem
I was looking for some information on 1-in-3 SAT and came across this paper, last updated 9 days ago, which claims that the Polynomial Time Hierarchy collapses "to the level above P=NP". That's quite exciting if you ask me, although I don't have the toolkit to understand the actual proof. My question is about something much simpler.
Specifically, in the abstract on arxiv, the author writes,
Our proof shows the structure formerly known as the Polynomial
Hierarchy collapses to the level above P=NP. That is, we show that
coNP⊆NP∖P.
Could anyone help me understand why these two statements are equivalent?
Specifically, in the abstract on arxiv, the author writes,
Our proof shows the structure formerly known as the Polynomial
Hierarchy collapses to the level above P=NP. That is, we show that
coNP⊆NP∖P.
Could anyone help me understand why these two statements are equivalent?
Solution
I believe the claim is more commonly written as $coNP \subseteq NP/poly$, but that of course does not immediately answer your question.
The fact that this implies that the polynomial hierarchy collapses is shown in Theorem 2 here:
Chee-Keng Yap. Some consequences of non-uniform conditions on uniform
classes. Theoretical Computer Science, 26:287–300, 1983. doi:10.1016/
0304-3975(83 ) 90020-8
If I understand correctly, $coNP \subseteq NP/poly$ is shown to be equivalent to $coNP/poly = NP/poly$ (unnamed corollary on page 292), and this would then imply $\Pi_3 = \Sigma_3$ (Theorem 2), implying collapse of the further hierarchy. For an actual proof, if you have access to the paper, I'll refer you there, I am not familiar enough with it to attempt an explanation now.
On an unrelated note, I believe the paper you are citing to be incorrect (but that would probably warrant a separate question?)
The fact that this implies that the polynomial hierarchy collapses is shown in Theorem 2 here:
Chee-Keng Yap. Some consequences of non-uniform conditions on uniform
classes. Theoretical Computer Science, 26:287–300, 1983. doi:10.1016/
0304-3975(83 ) 90020-8
If I understand correctly, $coNP \subseteq NP/poly$ is shown to be equivalent to $coNP/poly = NP/poly$ (unnamed corollary on page 292), and this would then imply $\Pi_3 = \Sigma_3$ (Theorem 2), implying collapse of the further hierarchy. For an actual proof, if you have access to the paper, I'll refer you there, I am not familiar enough with it to attempt an explanation now.
On an unrelated note, I believe the paper you are citing to be incorrect (but that would probably warrant a separate question?)
Context
StackExchange Computer Science Q#110880, answer score: 5
Revisions (0)
No revisions yet.