1
$\begingroup$

In a 2015 Quanta article talking about a breakthrough in the graph isomorphism problem, it was mentioned that graph isomorphism has a unique property where we have an interactive proof protocol for it. That is a prover can convince a verifier that two graphs are not isomorphic in polynomial time. That is, for the graph non-isomorphism problem a prover can convince an efficient verifier that two graphs are not isomorphic. We note that graph non-isomorphism is not known to be in either $NP$ or $BPP$.

But (as indicated by the Quanta article), is it the case that we have no known interactive proof protocol for NP-complete problems? That is, do we not have interactive proof protocols for problems like say the complement of Subset-Sum, where a prover needs to convince a polynomial-time verifier that there is no subset of the problem whose instance equals a target value?

And moreover, what would be the implication if there was, or was not such an algorithm for an NP-complete problem? If my understanding is correct, if there was such an algorithm, then it would prove that $coNP \subset IP$, but this is already known since $IP =PSPACE$, so I suppose I am confused on why this problem would be a big deal or not.

$\endgroup$

1 Answer 1

1
$\begingroup$

That article is talking about Arthur-Merlin protocols, which are a certain type of interactive protocol, with additional restrictions. IP = PSPACE doesn't apply, because not all interactive protocols are Arthur-Merlin protocols.

It is known that graph non-isomorphism is in AM. Also, it is considered unlikely that the complement of any NP-complete problem is in AM: if that were true for any NP-complete problem, then all of coNP would be contained in AM, which would imply some implausible consequences that complexity theorists don't expect to be true.

Consequently, it is considered unlikely that graph isomorphism is NP-complete. If graph isomorphism were NP-complete, then it would be a problem whose complement is in AM, proving that all of coNP is in AM, which would be surprising.

$\endgroup$
2
  • $\begingroup$ Thanks, so it looks like because $NP \subset IP$, if you have an interactive proof protocol for the complement of an NP-complete problem then this has no interesting ramifications? $\endgroup$
    – user918212
    Commented Oct 30, 2022 at 1:02
  • $\begingroup$ @user918212, correct. We already know how to construct an interactive proof for the complement of every NP-complete problem (using the construction that's found in the proof that IP = PSPACE, together with the trivial fact that co-NP is contained in PSPACE). $\endgroup$
    – D.W.
    Commented Oct 30, 2022 at 1:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.