Talk:Graph isomorphism problem

From Wikipedia, the free encyclopedia

This was exhibited as evidence of the power of such systems, since this problem is not believed to even be in NP.

Not believed by whom? What is the source of this dubious claim?

Graph nonisomorphism is in AM, and as far as I am aware, it is generally believed that AM = NP. This equality is in fact known to hold under reasonable hardness assumptions, much like in the case of P = BPP. -- EJ 00:40, 8 March 2006 (UTC)

My mistake. It would have been more accurate to say that it's not known to be in NP. Deco 21:43, 5 October 2006 (UTC)

In fact, it is more and more widely believed that GI lies in P. I fixed the sentence. Pascal.Tesson 02:45, 18 October 2006 (UTC)

[edit] Possible Proof of Polynomial Time Solution

There is a new paper (and algorithm) on the web claiming to prove that exact graph isomorphism is in P:

   Algorithm
   Proof

That first polynomial-time algorithm you cited relies on unproven assumptions. Deco 21:41, 5 October 2006 (UTC)

I think you're right about the first paper. However, the second claims to be a complete proof that graph isomorphism is in P. The paper refers to more theory than I've studied, so others will need to analyze it. Also, I'm retracting my proposed hashing algorithm, so I've removed it's links and discussion.

[edit] Subgraph Isomorphism Error

With regards to my edit. Ar first I took the original statement (that the Subgraph isomorphism problem is NP-complete). However, the article it points to clearly says that if that were the case, P=NP. More so, the graph isomorphism problem is in fact a special case of the subgraph isomorphism problem. If the Subgraph isomorphism problem was NP-complete, this problem would likely also be NP-complete (a fact that has not been proven). So yeah, I just wanted to point that out. --Stux 21:49, 25 October 2006 (UTC)

No, no, no. The subgraph isomorphism problem article clearly states that the problem is NP-complete, and that's correct (because the clique problem is its special case). Then it points out that NP-completeness of the graph (not subgraph) isomorphism problem would imply collapse of PH (not P=NP), which is, in fact, also mentioned in this article. -- EJ 12:26, 26 October 2006 (UTC)

Oh! I understand now. I see where I went wrong: when I read the last line in the subgraph isomorphism problem article, I misread it as saying that if the subgraph isomorphism problem is NP-complete, then P=NP; and then if Graph Isomorphism is NP-complete, then there would be a partial collapse in the complexity space. I had missed the first line which explained that sugraph isomorphism is NP-Complete the first time I read it. (I'm assuming the completeness half of the proof is simple: your G1=K_n you want to find as your clique in G2. Correct?) I also made the mistake of thinking I needed to reduce graph isomorphism to show completeness, instead of reducing 3-SAT, clique, or sugraph isomorphism into graph isomorphism to show that it is NP-complete.

So basically let me see if I understand things now: if another NP-complete problem is reduced to the Graph Isormorphism problem, thus showing that Graph Isomorphism is NP-Complete, then P=NP? However, if Graph Isomorphism is shown to be in P, then what would happen (that is, what are the consequences of GI=P)? Part of my confusion came from the Polynomial_hierarchy article, where the deficion of Π^p₂ was unclear to me. My guess is that Π^p₂ is just another name for P. --Stux 18:43, 27 October 2006 (UTC)

your G1=K_n you want to find as your clique in G2: yes, that's correct.

As for the second question: $\Pi^P_2$ is quite different from P. The first levels of the polynomial hierarchy are $\Sigma^P_0=\Pi^P_0=\mathrm{P}$ , $\Sigma^P_1=\mathrm{NP}$ , $\Pi^P_1=\mathrm{coNP}$ , $\Sigma^P_2=\mathrm{NP}^{\mathrm{NP}}$ (i.e., languages recognizable by a nondeterministic poly-time Turing machine with an NP-oracle), $\Pi^P_2=\mathrm{coNP}^{\mathrm{NP}}$ (i.e., complements of languages from $\Sigma^P_2$ ), and so on. If GI is NP-complete, then the polynomial hierarchy collapses to PH=AM=coAM, which also implies $\mathrm{PH}=\Sigma^P_2=\Pi^P_2$ and $\mathrm{PH}\subseteq \mathrm{NP/poly}=\mathrm{coNP/poly}$ . It is not known to imply P=NP. P=NP is a stronger assumption than the collapse of the hierarchy: if P=NP, then PH collapses (to P), but not necessarily vice versa.

As far as I know, GI=P does not have any unexpected consequences, which is after all one of the reasons why some people consider it plausible. -- EJ 11:41, 31 October 2006 (UTC)

I also wanted to mention that the line "Subgraph isomorphism is a generalization of the potentially easier graph isomorphism problem; if this problem is NP-complete, the polynomial hierarchy collapses, so it is suspected not to be." in the subgraph isomorphism problem article is ambiguous. It should specify what "this" is. But I want to be sure before changing it. --Stux 18:44, 27 October 2006 (UTC)

You are right, the sentence is confusing. I'll fix it. -- EJ 11:41, 31 October 2006 (UTC)

Retrieved from "http://en.wikipedia.org../../../g/r/a/Talk%7EGraph_isomorphism_problem_c4ed.html"

Talk:Graph isomorphism problem

From Wikipedia, the free encyclopedia

[edit] Possible Proof of Polynomial Time Solution

[edit] Subgraph Isomorphism Error

Views

Navigation

interaction

Search