2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Because $\mathrm{P} \subseteq \mathrm{coNP}$, we cannot have $\mathrm{coNP} \subseteq \mathrm{NP} \setminus \mathrm{P}$. $\endgroup$ – Pontus Jun 19 at 4:41
4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ you know, I kind of thought something was fishy when I couldn't find anyone else talking about this paper online -- but your answer makes sense regardless of the paper's overall validity, so thanks. $\endgroup$ – Joel Miller Jun 19 at 16:47
3
$\begingroup$

[...] the structure formerly known as the Polynomial Hierarchy collapses to the level above $\text{P}=\text{NP}$.

This claim makes no sense. If $\text{P}=\text{NP}$, then the whole polynomial hierarchy is equal to $\text{P}$ and there is no level above that.

That is, we show that $\text{co-NP}\subseteq\text{NP}\setminus{P}$.

$\text{co-NP}\subseteq\text{NP}\setminus{P}$ is unconditionally false, since $\text{P}\subseteq\text{co-NP}$ (and $\mathrm{P}\neq\emptyset)$.

I wouldn't recommend spending any time on this paper.

$\endgroup$
  • 1
    $\begingroup$ I wouldn't recommend spending any time on this paper. Agreed. $\endgroup$ – user53923 Jun 19 at 9:10
  • $\begingroup$ Now that I think about it, your statement "co-NP⊆NP∖P is unconditionally false, since P⊆co-NP" makes a lot of sense -- thanks for the advice that I don't look into the paper any further. I guess I assumed papers on arXiv were peer reviewed to some extent, but maybe they're not. $\endgroup$ – Joel Miller Jun 19 at 16:30
  • 2
    $\begingroup$ @JoelMiller ArXiv isn't peer-reviewed at all. Papers that are posted to ArXiv may subsequently be submitted to journals and peer-reviewed (e.g., all my ArXiv papers), but anyone who has posting rights to ArXiv can post whatever they want there. $\endgroup$ – David Richerby Jun 19 at 16:33
  • 1
    $\begingroup$ I'm not an expert on the subject area of this paper and I don't know or know of the author. On the one hand, user53293's explanation that "$\mathrm{NP\setminus P}$ is supposed to be $\mathrm{NP/poly}$ is somewhat convincing. But, still, it would be very strange for somebody who worked in that field to consistently make that mistake. As soon as you have a high-school understanding of what set difference is, and if you know circuit complexity, it's obvious that "slash poly" and "minus polytime" refer to two completely different concepts. $\endgroup$ – David Richerby Jun 19 at 16:37
  • 2
    $\begingroup$ @David Richerby I simply think that the author meaning NP/poly is the only explanation for the claims and "proofs" in the remainder of the paper. I fully agree that someone in the field should know better. And this is far from the only issue with the paper. $\endgroup$ – user53923 Jun 20 at 6:48

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.