Talk:Graph isomorphism problem/Archive 1

Context-free grammar isomorphism is GI-complete?

This seems dubious, since CFG grammar equivalence is undecidable. Will check tomorrow when I'm at work and have access to the given reference. Probably regular languages are instead meant here. — Preceding unsigned comment added by 83.254.71.96 (talk) 21:13, 8 June 2015 (UTC)

My guess: they really mean isomorphism, not equivalence. I.e. can you reorder the productions and rename the nonterminals so that you get exactly the same grammar (not just another grammar that recognizes the same language). —David Eppstein (talk) 06:30, 9 June 2015 (UTC)

I think you are right, that makes sense. The reference ( Zemlyachenko, Korneenko & Tyshkevich 1985) does not show the claim, but refers to another paper on this point: Hunt III, H.B., Rosenkrantz, D.J.: Complexity of grammatical similarity relations. Proc. Conf. Theor. Comput. Sci. Waterloo 139-145 (1977). I am not able to find it. A simmilar observation holds for isomorphism of balanced incomplete block designs, the current reference ( Zemlyachenko, Korneenko & Tyshkevich 1985) does not show the claim, but refers to another paper on this point: M. J. Colburn and C. J. Colburn, "The complexity of combinatorial isomorphism problems, Ann. Discrete Math., 8, 113-116 (1980). Which I am also unable to locate.

The Colbourn² paper is doi:10.1016/S0167-5060(08)70859-8 but I can only see an abstract there, not the full text. I also can't find the other one online at all. —David Eppstein (talk) 21:28, 9 June 2015 (UTC)

Low for ZPP^NP

The class GI is contained in, and in fact low for, ZPP^NP. This essentially means that an efficient Las Vegas algorithm with access to an NP oracle can solve graph isomorphism so easily that it gains no power from being given the ability to do so in constant time.

This 'point' seems to be poorly stated. I'm not sure exactly what result the author of this statement is trying to make, but seeing as GI is in fact in NP, a ZPP^NP machine already does have the ability to solve GI in constant time. To 'give' such a machine this ability is to give it something it already has. Perhaps it is meant to say that ZPP^GI = ZPP, or that NP^GI = NP? I'm not entirely sure what result is being referred to here.

Sorry if I didn't quite follow protocol in posting this, just trying to help improve the article.

Thanks for your feedback. The statement is correct as stated but perhaps poorly explained. The intent of the statement was that it gains no power from being given the ability to do so in constant time, which is not something an NP machine can do (it requires polynomial time). I'm not sure how to clarify this. See the linked article on "low" for more information. Dcoetzee 10:22, 17 June 2007 (UTC)

Claim about problem not believed to be in NP

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)

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.

What about this new reference:

   [1]

??? — Preceding unsigned comment added by 2001:638:807:20E:390F:FAE4:A580:8AE3 (talk) 11:23, 28 June 2012 (UTC)

I'm skeptical that the claims in that paper are true and I'm skeptical that it is a reliable source. In particular, I don't see why the sorting procedure they describe produces a canonical form (that is, why should permuting a matrix arbitrarily and then sorting it as described always produce the same sorted matrix?). —David Eppstein (talk) 18:17, 28 June 2012 (UTC)

Some additional info about the above reference that supports the idea that it is not a reliable source: the first author is the founder and director of "The Institute of Mathematics", where the paper is published. All other publications from this organisation are from the same author, and there is a detailed account of arguments over the author's claimed proof of the Four Colour Theorem in 2000. —Iainmcgin (talk) 18:03, 16 November 2012 (UTC)

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 _{2}^{P}$ is quite different from P. The first levels of the polynomial hierarchy are $\Sigma _{0}^{P}=\Pi _{0}^{P}=\mathrm {P}$, $\Sigma _{1}^{P}=\mathrm {NP}$, $\Pi _{1}^{P}=\mathrm {coNP}$, $\Sigma _{2}^{P}=\mathrm {NP} ^{\mathrm {NP} }$ (i.e., languages recognizable by a nondeterministic poly-time Turing machine with an NP-oracle), $\Pi _{2}^{P}=\mathrm {coNP} ^{\mathrm {NP} }$ (i.e., complements of languages from $\Sigma _{2}^{P}$), and so on. If GI is NP-complete, then the polynomial hierarchy collapses to PH=AM=coAM, which also implies $\mathrm {PH} =\Sigma _{2}^{P}=\Pi _{2}^{P}$ 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)

To clarify this succinctly: the graph isomorphism is a special case of the subgraph isomorphism problem, and so potentially easier (the case where the subgraph can only be the entire graph). If the subgraph isomorphism problem is in P, then P=NP=PH, since it's NP-complete. If the graph isomorphism problem is in P, then no collapse is known to occur. If the graph isomorphism problem is NP-complete, the polynomial hierarchy collapses to $\Pi _{2}^{P}$; that is, $\Pi _{2}^{P}=PH$. This does imply that P=NP or P ≠ NP, but it would still be pretty darn surprising, as it would imply essentially that all polytime alternating Turing machines with a finite number of alternations can be simulated by an ATM with only 2 alternations. Dcoetzee 07:46, 25 May 2007 (UTC)

Rooted trees

The algorithm in Graph isomorphism problem#Example: Rooted trees is not as trivial as it seems. Several claims in its description require mathematical proofs. Therefore this section requires a references. Twri (talk) 23:30, 23 June 2009 (UTC)

OK. Removed. Here is an exercise: find a counter-example to the algorithm below. Twri (talk) 23:51, 23 June 2009 (UTC)

Exercise 2: Find the smallest counter-example. Twri (talk) 23:51, 23 June 2009 (UTC)

Exercise 3: Find the largest counter-example :-) Twri (talk) 23:51, 23 June 2009 (UTC)

Exercise 4: Find how to fix the algorithm. - Altenmann >t 00:06, 24 June 2009 (UTC)

Exercise 5: Find the source the contributor thought describes the algorithm. - Altenmann >t 00:06, 24 June 2009 (UTC)

The source for this was some lecture notes on the topic - I unfortunately did not note where I found them. The point is to give a simple example of a graph isomorphism algorithm. It does need some cleaning up... Dcoetzee 00:11, 24 June 2009 (UTC)

The idea is sound, however as in maths goes, if you miss a link, the whole design collapses. Here is a counter-example.

tree_1: level_3: 5 vertices, level_2: 2 vertices which link to 1 & 4 level_3 vertices, level_1 - root

tree_2: level_3: 5 vertices, level_2: 2 vertices which link to 2 & 3 level_3 vertices, level_1 - root

After first iteration, on the second level the "long labels" will be T_1: (1, 1111) and T_2: (11, 111) resp. (or whatever else for other labeling conventions). They turn into exact same "short labels" T_1: (1, 2) & T_2: (1, 2) .... Continuing is useless. - Altenmann >t 00:26, 24 June 2009 (UTC)

At first I thought that a simple remedy would be a known trick of joining two rooted trees into one by adding an extra root vertex. Now my counter-example fails: at first step we will have (1, 1111, 11, 111) ->sorted-> (1,2,3,4). A the second step we will have (14, 23), i.e., old "roots" receive different labels, hence their subtrees are nonisomorphic. But again, thus fix still requires a proof, i.e., a valid reference. - Altenmann >t 00:33, 24 June 2009 (UTC)

Still, an additional nontrvial effort is required to prove that the whole algorithm may be made to run in linear time. - Altenmann >t 00:38, 24 June 2009 (UTC)

Example: Rooted trees

There is a particularly simple algorithm for determining if two rooted trees T and T' are isomorphic. First, assume that T and T' have the same number of vertices and the same height (otherwise they are not isomorphic). The vertices can be grouped into levels, sets of vertices that are the same distance from the root; since distance from the root is preserved by isomorphism, vertices in T must correspond to vertices in T' at the same level. We process the tree beginning with the bottom level and moving upwards, systematically assigning a label to each vertex such that two vertices have the same label if and only if the subtrees rooted at those two vertices are isomorphic.

Suppose v is an unlabelled vertex. Since the algorithm processes the tree bottom-up, all its children already have labels; assign v a temporary long label by sorting and concatenating the labels of its children. Next, sort all vertices at the current level by their long labels; then, assign fresh short labels to each vertex by numbering them from zero and giving identically-labelled vertices the same number. If at any level the final sorted set of short labels is different in T and T', then they are not isomorphic; otherwise the two roots will be assigned the same label and they are isomorphic.

Sorting the labels with a simple comparison sort, this algorithm requires Θ(n log n) time, where n is the number of vertices; it can be made to operate in O(n) time by careful use of bucket sort and radix sort.

This algorithm can be used to find isomorphism of general trees by noting that an isomorphism must map the center of T to the center of T'; the center of a tree has at most two vertices, so there are at most two ways of selecting the root nodes.

References tag on Applications section

(Re: Reverted 1 edit by Tim32; I don't see a problem with the refs. Please discuss on talk)
The problem is that the Applications section for chemical GI application is incomplete: only SMILES and InChI are noted, but these methods are not useful to solve many important tasks in computer chemistry, so strong and adapted for chemistry GI algorithms are necessary. I found one: M.I.Trofimov, E.A.Smolenskii, Russian Chemical Bulletin, 2005, Vol. 54, 9, 2235. http://dx.doi.org/10.1007/s11172-006-0105-6 Nobody found more, for example Arjeh M. Cohen , Jan Willem Knopper and Scott H. Murray cited only that article in Automatic Proof of Graph Nonisomorphism, Mathematics in Computer Science, 2008, doi 10.1007/s11786-008-0052-8 At the same time, a lot of heuristic algorithms had been offered for chemistry, but they were not proved and not so effective. --Tim32 (talk) 18:51, 24 June 2009 (UTC)

Be careful with WP:COI. I think it is pretty clear that Cohen, Knopper, and Murray were just citing one article per large application in their paper and made no attempt to be exhaustive. Please do not misrepresent sources.

Similarly, the wikipedia article is trying to indicate important applications of the graph isomorphism problem in science, not trying to explain molecular databases and certainly not trying to explain cutting edge techniques for searching for molecules. Adding more information on molecular databases would degrade this article. Please do not use articles as coatracks for your work. JackSchmidt (talk) 19:14, 24 June 2009 (UTC)

A more exhaustive treatment of computer chemistry may be suitable for another article, as this article is intended to cover the problem from a graph theory and computer science perspective. Dcoetzee 21:51, 24 June 2009 (UTC)

• "Adding more information on molecular databases would degrade this article" -- only graph canonization approach is noted for chemistry in this section, it is extremely incomplete! A few words more would not degrade this article. This your reason is nonsence. Also, you wrote "the wikipedia article is trying to indicate important applications of the graph isomorphism problem in science" - graph canonization approach is not more important for chemistry than other approaches. I made a link for important source, so there is no real conflicts, and so your ref. to WP:COI is invalid for this case, it is your unproved suspicion only.--Tim32 (talk) 11:19, 26 June 2009 (UTC)

• "I think it is pretty clear that Cohen, Knopper, and Murray were just citing one article per large application in their paper and made no attempt to be exhaustive. Please do not misrepresent sources." -- The fact is that six months some of editors of GI article in Wiki made many attempts to be exhaustive, but they found nothing more (again many thanks for these attempts -- this info was very useful for my sci.researches :). So, I can repeat your words: please, do not misrepresent sources.--Tim32 (talk) 11:19, 26 June 2009 (UTC)

• "A more exhaustive treatment of computer chemistry may be suitable for another article" -- it was done: see, computer chemistry, mathematical chemistry etc.--Tim32 (talk) 11:19, 26 June 2009 (UTC)

I agree with the editors who feel that the extensive discussion on cheminformatics and mathematical chemistry seems out of place. I would suggest a one line explanation of the application in these fields, much like the existing one liner about electronic design automation: "In electronic design automation graph isomorphism is the basis of the Layout Versus Schematic (LVS) circuit design step, which is a verification whether the electric circuits represented by a circuit schematic and an integrated circuit layout are the same." --Robin (talk) 15:31, 10 July 2009 (UTC)

You wrote: "I agree with the editors who feel that the extensive discussion on cheminformatics and mathematical chemistry seems out of place." What is the reason for your agreement? Is it feeling only? And, please, give any ref. for your addition.--Tim32 (talk) 16:53, 10 July 2009 (UTC)

See WP:TE, specifically the part about "You challenge the reversion of your edits, demanding that others justify it". —David Eppstein (talk) 16:58, 10 July 2009 (UTC)

David, I did not understand how is "electronic design automation" connected with chemical applications? ;)--Tim32 (talk) 17:24, 10 July 2009 (UTC)

They are both examples of areas in which graph isomorphism has some level of application but which are not central to the topic of graph isomorphism? —David Eppstein (talk) 18:10, 10 July 2009 (UTC)

Ok, and what else? I agree that the statement: "In electronic design automation graph isomorphism is the basis of the Layout Versus Schematic (LVS) circuit design step, which is a verification whether the electric circuits represented by a circuit schematic and an integrated circuit layout are the same." May be added, but any ref. would be necessary. However it is another area for application. You wrote a paper about GI in computer animation. Yes? You also can add this ref. to this section. More info is necessary for this section. What is the problem? Please, explain.--Tim32 (talk) 18:30, 10 July 2009 (UTC)

PS. Application's areas are central to the topic of graph isomorphism applications!--Tim32 (talk) 18:49, 10 July 2009 (UTC)

It is unfortunate that you still fail to see the problem. I'm going to attempt to explain the problem, with simple English and no complicated Wikipedia policy links. The application you mention is not central to the topic of GI. A one line description which links to the relevant articles is more appropriate, rather than a lengthy discourse on the state-of-the-art in Chemistry. This information belongs to the article on mathematical chemistry (or whatever the application is), not this article. If we were to add everything that is tangentially related to GI, then half of computer science would become part of this article. Do you see the problem? --Robin (talk) 19:00, 10 July 2009 (UTC)

No, I do not see any problem here. I am not sure that "If we were to add everything that is tangentially related to GI, then half of computer science would become part of this article." The current size of Applications section is very small now, more examples from different areas are necessary. GI testing is very important for modern chemistry, but noted graph canonization approach via SMILES and InChI does not work for many important cases. Also it is not very effective for computing. Again, applications are central to the topic of graph isomorphism applications. If and when the size of the section will be too large then we can make single article "GI applications."--Tim32 (talk) 08:52, 11 July 2009 (UTC)

My impression, by the way, from seeing some of the work of Pierre Baldi (faculty in my department who works on this sort of thing) is that Tim's statement above "GI testing is very important for modern chemistry" is not really true. What's important, for chemistry database searches, is a closely-related but different problem, graph canonization: transform a given graph into a canonical form such that any isomorphic graph will be transformed into the same form. It would be ridiculous to apply a full GI algorithm between your search target and every molecule in a database, even though each individual test is an easy and quickly-solved GI problem. Rather, what you want to do is to convert your target into a canonical form and then find that canonical form in the database. Also, it's likely that what you want to do is find partial matches rather than exactly the same chemical; again, that's not graph isomorphism but a related problem, subgraph isomorphism, and again it may be attacked by finding canonical forms for the subgraphs and searching for them in the database. —David Eppstein (talk) 16:17, 11 July 2009 (UTC)

Yes, David, yes! You are right – graph canonization is very attractive for chemistry. Thank you for very interesting note. But first of all, let’s note that this is your original research (your impression only), and so it is out of scope in Wiki. Yes, there are many investigations, where different graph canonization approaches had been suggested for chemistry. Unfortunately, exact graph canonization may be more hard task then direct GI testing. At the same time many heuristics methods were introduced. For example, some modern SMILES programs have problems for cuneane – as you can see it is very simple regular graph (I mean carbon atoms only). But again graph canonization is still very attractive, however here in Wiki we have to note opposite point of view as well.

About subgraph isomorphism (SI): as you know it is another problem. In contrast with GI we know that SI is in NP. Yes, SI is very important for chemistry also. But fragments search in chemical database should be solved via another methods, because it is NP hard problem. For example, many of molecular graphs are trees and many of molecular graphs are planar graphs. GI test for such graphs is very fast.

Key generation for chemical database is special problem. Yes, it may be solved via canonical labeling, but may be solved via indices (topological etc.). Please, see my paper for more info.--Tim32 (talk) 19:52, 11 July 2009 (UTC)

Re "In contrast with GI we know that SI is in NP.": please get your terminology straight. GI and SI are both in NP, as is everything in P as well. SI is NP-complete, meaning that it's unlikely to be in P. But that says little or nothing about its computational difficulty in chemical tasks since the graphs on which it is hard may not be the ones arising in that application. —David Eppstein (talk) 19:56, 11 July 2009 (UTC)

Ok, I hope here we will not discuss "P=NP?" etc.:) Anyhow, for real applications GI and SI are different tasks very often. Not only for database management, but also, for example, for molecular graphs generation. Have you more to ask me?--Tim32 (talk) 20:20, 11 July 2009 (UTC)

You wrote: "see my paper for more info" What paper did you mean? --EsfirK (talk) 19:06, 23 July 2009 (UTC)

• Please, see: http://dx.doi.org/10.1007/s11172-006-0105-6 --Tim32 (talk) 19:30, 23 July 2009 (UTC)

I looked at the free preview of the article - it is hard to get a real good sense of the article just from one page. Get me link to Russian translation of the article. I'll try to find it in Moscow's libraries. Does this method deals with heteroatoms (O,N,S etc.)?--EsfirK (talk) 21:04, 27 July 2009 (UTC)

• Izvestiya Akademii Nauk. Seriya Ximicheskaya: Известия Академии Наук. Серия химическая. 2005, N 9, 2166-2176.
• Yes, this works for heteroatoms, please, see p.2169 in Russian issue or p.2238 in English.--Tim32 (talk) 12:54, 28 July 2009 (UTC)

Thanks! I've read this article. IMHO - you are quite right. It's the original method. It must be noted here, and I'm so surprised that it's not... --EsfirK (talk) 16:17, 14 August 2009 (UTC)

Thank you for your interest in this paper, EsfirK! Unfortunately, I see that your or somebody oppinion has no sense for wiki obscurantists :( --Tim32 (talk) 16:11, 15 August 2009 (UTC)

David Eppstein: Content-free citation of a paper by a notorious self-promoter.)

What's the matter, David? Why did this reference dissappear? Well, the article looks like awfully incomplete. It's Wiki or "I do as I want"? (Sorry, you may not know such Russian proverb). Why you are so sure that this reference is only "Content-free citation of a paper by a notorious self-promoter"? I now a lot of such citations - please see article about Prince Wolkonsky for sample. Or - may be it's only a little of envy? Are you scientist? --EsfirK (talk) 15:55, 15 August 2009 (UTC)

I only want to note that David Eppstein offended me by "notorious self-promoter" -- it is forbidden as in wiki as well in internet! Shame on you David! --Tim32 (talk) 16:05, 15 August 2009 (UTC)

Tim32, you appear to be a single-purpose account whose sole purpose is to edit articles related to chemical applications of graph isomorphism and who has spent large amounts of effort attempting to insert references to papers by Trofimov (who your user page identifies yourself as) into this article. You'll forgive me if I don't write out the same thing in detail every time I refer to it, but rather abbreviate it as "notorious self-promotor". If that characterization offends you, you're welcome to change your ways and spend more effort making edits that are less self-serving. —David Eppstein (talk) 20:27, 16 August 2009 (UTC)

David Eppstein, see list of my important contributions to wiki-pages on my user page: there is a lot of articles! It is not single-purpose account. And the fact is that the Community is agreed with majority of my editions. It is clearly in good faith. So, please do not use "notorious self-promoter" to describe me. It is a violation of our policies and guidelines on assuming good faith and civil behavior. Moreover, please, do not use these worlds if somebody else is agreed with my oppinion and made any edition which edition links to my paper. I did not do this edit!--Tim32 (talk) 23:28, 16 August 2009 (UTC)

Repeated insertion of completely uninformative sentence about non-notable paper.) - ??? David, would you be so kind as to prove these your words? Non-notable!!! about Academician issue! Have you ever read this article?--EsfirK (talk) 19:51, 16 August 2009 (UTC)

No, I haven't read it. Google scholar tells me there are over eight thousand articles about graph isomorphism. Obviously we can't cite them all, and you have provided no reason why this paper is any more important and worth citing than 7,999 others. Further, the sentence you used to cite it doesn't say anything about its actual content, only that it is a paper about graph isomorphism. I consider this more a form of marking territory than doing anything to inform the readers of the article, and I plan to continue reverting it. PS for future reference, you are misspelling the word "foolish". —David Eppstein (talk) 20:18, 16 August 2009 (UTC)

No, I haven't read it - !!! no comments. Hi, David! It's coool! "I've not read Pasternak but I say" - if you know a little the Russian literature history, you will laugh with me... May be, the number of articles devoted this problem is more than. But this one relatives to chemistry! And what does it mean - "I plan to continue reverting it" - ? I think, you are interested in improving the article. And now you say - no, I will insist on my oppinion, without reading the article. It's science? I doubt... It's religion. Arguments, please! P.S. For future reference, you are misspelling foolish words "non-notable paper". --EsfirK (talk) 21:10, 16 August 2009 (UTC)

Even assuming good faith, the actions of Tim32 and EsfirK seem extremely suspicious. Your repeated references to Russian proverbs and literature is completely uninformative and extremely annoying. Your lack of understanding of the English language and inability to write coherent, grammatically correct sentences reduces the possibility of clear communication. If I spoke Russian, I would probably explain my views in Russian so that we can have some meaningful conversation here.

I think I'm one of the typical readers of the article -- someone who understands computer science in general, but does not do research on GI. I find you (Tim32 and EsfirK) very biased and just trying to promote a paper of Tim32, and trying to fill this GI article with information about Mathematical Chemistry. This is not the place for that! This is an article on GI. A one line explanation of the application and a link to an article which explains this is all that is needed. I also plan to continue reverting any uninformative and non-notable edits by you two.

Lastly, I don't want to make any sockpuppet/meatpuppet accusations against EsfirK, but notice that all the other editors of this article are strongly against the actions of you two (Tim32 and EsfirK). This should be very clear indication that you are doing something wrong. David Eppstein seems to be doing his best to try to reason with you two and explain the situation at hand, I applaud his effort. Finally, stop this obvious self-promotion and childishness. You are a scientist. If your work is good, people will read it. You do not need to have it advertised on Wikipedia in this underhanded manner. Be proud of being a scientist. --Robin (talk) 19:24, 17 August 2009 (UTC)

Robin, it is not self-promotion, but WP:NPV.--Tim32 (talk) 11:09, 18 August 2009 (UTC)

PS. BTW, do you think that your expression "lack of understanding of the English language " is good English? ;)--Tim32 (talk) 11:09, 18 August 2009 (UTC)

Robin, stop personal attack! I have a right to choose any example from history of any country - US or Russia or Holland. And Pasternak was Nobelist - so this is notable person for world history. And if you do not know about him and his life - it's your problem. You can read about him - for example in Wiki Boris Pasternak. And finally - I'm not author of this article so what self-promotion do you mean? --EsfirK (talk) 13:46, 20 August 2009 (UTC)

Your digressions into Russian literature are not helping your case or helping the point you are trying to make. I don't know how to make it clearer to you.

The last few sentences about self-promotion were directed at Tim32, who is an author of the paper. I thought that was clear from context.

Lastly, stop re-adding the reference. Add it back only if it gains consensus here, in the talk page. I see no support for it other than the author of the paper Tim32, and you. --Robin (talk) 14:23, 20 August 2009 (UTC)

Regarding possible sockpuppet/meatpuppet connections between EsfirK and Tim32, I observe that EsfirK shows a marked interest in the history of Russian theatre, and in particular, in Serge Wolkonsky and relatedsubjects. The same editing interests were displayed by the creator of the Serge Wolkonsky article, User:Mart071, who self-identifies as "Mary Trofimov" (and yes, they know each other with M. I. Trofimov[2], so they are likely related). I don't believe for a second that this is just a coincidence. — Emil J. 16:10, 21 August 2009 (UTC)

The same goes for 92.243.181.135, of course. — Emil J. 16:18, 21 August 2009 (UTC)

Excellent detective work, EmilJ. --Robin (talk) 20:24, 21 August 2009 (UTC)

Excellent defamation!!! I think you are DE clone, for example ;) Stop personal attack! --Tim32 (talk) 20:37, 21 August 2009 (UTC)

EmilJ! Good time! Waw! About Prince Serge Wolkonsky knows a lot of people even in USA :-), the country where he dead and was buried. Mary Trofimov is one of the most specialist onto this field. Many thanks that you think we are the one person!!! And then, many people are interesting of Russian history - literature, ballet and so on.--EsfirK (talk) 16:30, 21 August 2009 (UTC)

Thanks again for your message to my talk page, EsfirK,

• Me is Mary Trofimov! What's the matter? I do not know about graphs (comtes, if you please, or The Count of Monte Cristo). I do know only Princes!:-) Which mathematical nonsense! Just because you've written such foooooolich words - I'll undo your "undid"! And anyone from these users could ask me - who am I? I have My Talk Page!!! I have a lot of publications -and no one is dedicated to who-is-that graphs... Please, do not disturb me about these strange so-called "graphs" any more. If EsfirK is interested in Prince Serge Wolkonsky she is welcome - I noted her editions, as the best. But why you consider my person here? I think that division by zero is ok! Any question more? I udndid your revision, because of only I did not read the paper like you!!! Take off your hands from Prince Serge Wolkonsky! --Mart071 (talk) 21:38, 21 August 2009 (UTC)

Dear EmilJ! May be I am Mary Trofimov as well? ;-)))) Are you sure?! ;-)))--Tim32 (talk) 16:35, 21 August 2009 (UTC)

Robin, you wrote "Your digressions into Russian literature are not helping your case or helping the point you are trying to make." Can I ask "Why?" Please read:

"Although none of his Soviet critics had the chance to read the proscribed novel, some of them publicly demanded, "kick the pig out of our kitchen-garden," i.e., expel Pasternak from the USSR. This led to a jocular Russian saying used to poke fun at illiterate criticism, "I did not read Pasternak, but I condemn him". Doctor Zhivago was eventually published in the USSR in 1988". (Boris Pasternak)

As Wiki-editor you must be informed in excellent situations from world history, and you must not repeat the same terrible errors which errors had been done before you. Perhaps you do not imagine how you look like former Soviet censors!

Didn't you think that you just now you looks like these Soviet critices who did not read the paper by T&S, but you condemn them. Why you do it? As, I see you have no arguments, you wrote:

"The last few sentences about self-promotion were directed at Tim32, who is an author of the paper."

Have you any argument against my edit? Note, Tim32 did not the edit you'd removed – it was my edit! And before you will have any strong argument I'll save this edit!!! My strong argument is WP:NPW – have you any?! As you'd written himself "Be proud of being a scientist." And so if you have no any valid argument – be proud, to agree that you have no arguments – you losed this party!--EsfirK (talk) 22:22, 20 August 2009 (UTC)

Review of Trofimov and Smolenskii

Since we now have two usernames attempting to add the same Trofimov and Smolenskii paper (per WP:AGF I'll assume these are really two different people), since these editors both don't seem to understand the need to justify adding the paper and rather insist that anyone removing it justify its removal, since these editors were decrying the fact that I hadn't actually read the paper (not needing to read it to see that its presence here had not been justified), and since I do have some professional expertise in graph isomorphism that should make it easier for me to read the paper than others, I thought it might save other editors some effort if I read it and reviewed it here.

Review of Trofimov and Smolenskii, "Application of the electronegativity indices of organic molecules to tasks of chemical informatics", Russ. Chem. Bull. 54:2235–2246, 2005.

The quality of the English in the paper is bad, to the point of being quite difficult to understand. For instance, early in the paper one finds the sentence "It is well known that the structural formula of a compound can be graphically represented in different manner." Besides the classic Russian error of omitting the article on the final noun, it is completely unclear what "in different manner" adds to the sentence, and "graphically" does not mean the same thing as "graph theoretically", rather it means something having to do with a visual representation. The sentence would be much more clearly written "It is well known that the structural formula of a compound can be represented as a graph." Similar problems exist in most sentences of the whole paper.

The application of graph isomorphism to chemistry is not justified in this paper, but merely asserted, in the second sentence, in a classic example of begging the question. This sentence asserts that the first step of a "database filling query" (what does "filling" add to the meaning here?) must be to find structures in the database that are isomorphic to the structures in the query. There are a lot of dubious assumptions encapsulated in this sentence, beginning with the one that a query must itself encode graph structures. But taking it as a given, I have to assume that the use of the plural indicates that the structures in question are not the whole query and the whole molecule in any given database entry, for if that were the case there would be only one structure in the query and one matching structure in the database. Rather, this sentence seems to be referring to some form of subgraph isomorphism, making the motivation for the graph isomorphism algorithms discussed in this paper quite dubious.

The graph isomorphism algorithm described in the paper begins by computing some simple indices (incorporating, for instance, the length of the shortest path through each edge) as a quick filter against isomorphism: if the indices differ, the graphs are not the same. The main algorithm involves a numerical formula for a numerical value for each vertex of a vertex-weighted graph, computed by solving a system of linear equations involving the adjacency matrix of the graph (formula 2). Although described in chemical terms as an "electronegativity", the calculation may be performed for an arbitrary graph without regard to any chemical origin of the graph. If a vertex has a unique numerical value, its isomorphic copy may be easily identified; otherwise, the algorithm recurses within the smallest subset of equivalent vertices, updating the weight of each vertex in the set in turn, and calling the same algorithm recursively on each reweighted graph. In the sense that this algorithm uses numerical matrix information to distinguish the vertices when possible, reducing the need for backtracking, this is not unlike the algorithm of Schmidt and Druffel (JACM 1976), although the detailed numerical calculations differ. For that matter, earlier, Turner (SIAM J. Appl. Math. 1968) already searched unsuccessfully for matrix functions that could be used to characterize vertices for graph isomorphism, so an approach based on this idea cannot be thought of as particularly novel; what matters more, in order to evaluate the quality and impact of the Trofimov and Smolenskii paper, is whether the details of their approach lead to improved performance compared to existing algorithms, either theoretically or empirically.

In this respect the paper completely fails: the bulk of the paper consists of empirical tests only of the new algorithm. There is no new theoretical time analysis and there is no attempt at comparison with standard algorithms. Indeed, timings were included only for the first set of tests, and excluded for the remainder with a vague statement that "other service operations took a rather long time". Rather, the empirical testing provides large tables of the maximum recursion depth and number of iterations of the algorithm, almost completely useless data.

To conclude: the presented method probably works acceptably well, and is likely novel in its particulars, but there is no reason to believe that it's better than other standard algorithms and it is described so unclearly that it would be difficult for anyone else to reconstruct the same algorithm from this paper. No new theory is presented, most of the experimental data is useless, and there is no way to tell from this paper whether the method improves over methods already known 30 years prior to its publication. The motivation from chemical informatics is thin (since subgraph isomorphism not graph isomorphism seems to be the more important problem there) and this paper does little to explain why subgraph isomorphism is important in this application; it merely asserts that this importance is well known. The lack of citations indicates that the paper has not made a large impact in any branch of academic endeavor, and its bad writing and specialized content make it unsuitable as a general introduction to chemical applications of graph isomorphism. In short: it is a bad academic paper, not unlike most other academic papers (see Sturgeon's law) but not deserving to be cited here through any merit or priority. —David Eppstein (talk) 02:15, 17 August 2009 (UTC)

Springer wrote about the journal following description:

“Publishing nearly 500 original articles a year, Russian Chemical Bulletin is a prominent international journal. The coverage of the journal spans practically all areas of fundamental chemical research and is presented in five sections: General and Inorganic Chemistry; Physical Chemistry; Organic Chemistry; Organometallic Chemistry; Chemistry of Natural Compounds and Bioorganic Chemistry.The Bulletin's International Advisory Board is comprised of eminent scientists from Europe, USA and Japan. Contributed by leading scientists from Russia and throughout the world, all papers are rigorously refereed and edited to the highest international standards.The Journal was founded in 1936 and has been published in English since 1951.Russian Chemical Bulletin is a translation of the peer-reviewed Russian journal Izvestiya Akademii Nauk: Seriya Khimicheskaya.” http://www.springer.com/chemistry/journal/11172

Of course, very often English in translated paper is not so good as in original English paper, but this paper had been translated by the best interpreters from editorial of the journal. So, I do not think that the quality of the English in the paper is so bad as you claimed. Interesting to note that as soon as you did this your clime you just did a big mistake: the authors definitely had written about graphically represented structural formula, i.e. about picture, not about abstract graph! So, the problem is that you did not wish to understand the paper. You did not wish to read exact text that had been printed in this paper, but you wish to find there your own dreams. Your general dream is that subgraph isomorphism is much more important for chemistry ruther than graph isomorphism – this is your own WP:OR onlly. For example, for Wiki user is important to find phenol (i.e. to find graph), ruther than to find O-H subgraph in phenol and in many other compounds :-)

At the same time in your review you used statements which statements are quite difficult to understand, for instance:

“this is not unlike the algorithm of Schmidt and Druffel (JACM 1976), although the detailed numerical calculations differ”

And you said nothing about important details of the numerical calculations, which details are significant for understanding why this approach is original. You said few common words only about matrix functions and did another mistake:

“an approach based on this idea cannot be thought of as particularly novel”

Another your dream is about vague statement that "other service operations took a rather long time" – the exact statement is: “The results of further tests listed in Tables 2—4 provide no elapsed time measurement data, because specific input—output procedures and other service operations took a rather long time.” (p.2240). The Table 1 has timing for 93160816 graphs, it is quite sufficient. Table 3, for example, has test for 100000 graphs only, which graphs were read from hard disk and it is obviously that timing which includes such slow reading would be a nonsense!

In conclusion you wrote:

“the presented method probably works acceptably well, and is likely novel in its particulars, but there is no reason to believe that it's better than other standard algorithms”

Which standard algorithms did you mean? Do you know many “standard” algorithms which are adapted for chemistry (heteroatoms, double bonds, etc.) and adapted for chemical database management system? (key generation, etc.)

You wrote:

“The application of graph isomorphism to chemistry is not justified in this paper”

The paper has a list with 31 references, which references are very important for GI chemical applications, all of the sources had been discussed in this paper. Also, some chemical structures which are interesting for GI chemical applications had been discussed as well: cuneane and C23O (p.2238), cyclobutane, cyclopentane, and cyclohexane, cubane, dodecahedrane (p.2241) and also the “Proportion of regular graphs” (Table 5) has been discussed, etc. Some important chemical indices (Hosoya index and its modifications, Wiener index and its extension and the electronegativity) have been discussed as well. Previously you wrote that you have no professional expertise in chemical areas (for example for Kekule structures), this fact explains your dreams such as noted “subgraph isomorphism” dream.

And you wrote:

“it is described so unclearly that it would be difficult for anyone else to reconstruct the same algorithm”

See acknowledgments (p.2242): nobody from noted well-known specialists said that this algorithm may be difficult to reconstruct. Perhaps, you have no experience in practical programming area? But you are welcome: please, report number of algorithm (there are 5 algorithms in this paper) and number of line of the listing which is difficult for you. I will explain it.

This paper was rigorously refereed (see, cited description by Springer) and I think that these reviews are more important than this your “review”, where you did not write about this paper, but only write about your own dreams and original researches. So, I do not think that “it is a bad academic paper”, but I see you did very bad review. Also, I see that you spent very short time for reading and no time to think about, this fact explains why you understood nothing.--Tim32 (talk) 18:28, 17 August 2009 (UTC)

Tim32, you have to justify to everyone else why this paper should be included here, not the other way around. The burden of proof is upon you. You have to convince us, the other editors, that you paper deserves to be mentioned. Just adding it over and over will not help. We'll keep removing it. Give reasons (sensible ones, and in English please) and also explain why the reference should be present in this Wikipedia article. --Robin (talk) 19:27, 17 August 2009 (UTC)

Applications section for chemical GI application is incomplete: only the graph canonization approach is noted: “SMILES and InChI, designed to provide a standard and human-readable way to encode molecular information”, but “Different chemical nomenclatures take into account specific features of human perception and provide a compromise between the "strictness" and "convenience". Such a compromise is admissible for human practice but not always appropriate for computer implementation.” (Trofimov and Smolenskii, p.2235) The alternative approach via electronegativity indeces usage was described by Trofimov and Smolenskii. This paper had been noted by Arjeh M. Cohen , Jan Willem Knopper and Scott H. Murray (doi 10.1007/s11786-008-0052-8). And this approach has to be noted here as well for WP:NPV. WP:NPV is strong reason! -- More advanced scientific discussion which method is better and for which case would be redundant for Wiki talk page.--Tim32 (talk) 10:28, 18 August 2009 (UTC)

Please notice that WP:NPV has a section WP:UNDUE. As it was mentioned here several times, Trofimov's fails the "undue weight" criterion: his view is a negligible minority, unconfirmed by any published independent diligent reasearch. Twri (talk) 19:08, 25 August 2009 (UTC)

Published independent diligent reasearch is Arjeh M. Cohen , Jan Willem Knopper and Scott H. Murray, Automatic Proof of Graph Nonisomorphism, Mathematics in Computer Science, 2008, doi 10.1007/s11786-008-0052-8 --Tim32 (talk) 20:12, 25 August 2009 (UTC)

I did not see consensus here. --EsfirK (talk) 16:05, 21 August 2009 (UTC)

The fact, that this problem is in P is explained in a more readable form in http://arxiv.org/abs/0711.2010v4 . (of course, it is written later than a paper of Trofimov and Smolenskii) 92.62.52.226 (talk) 07:55, 11 September 2009 (UTC)

See, ref. 7 in http://arxiv.org/abs/0711.2010v4 -- this is ref. to the paper of Trofimov and Smolenskii.--Tim32 (talk) 10:45, 11 September 2009 (UTC)

State of art section

I added the section and corrected erroneous lead. The Babai-Codenotti paper makes it clear that the best algorithm is due to Luks, even if it is only published in Babai-Kantor-Luks paper (1983). With all due respect, Johnson's 2005 column get the complexity right but misattributes it to Babai-Luks where a slightly weaker bound was obtained (by a poly-log term in the exponent). I know, it's confusing but that's how it is and can be checked directly. Feel free to ask me to provide more details if you are confused - I will watch this talk page.

About practical algorithms - it's an important observation that McKay's algorithm is exp in teh worst case - this is due to Miyazaki (1997). I encourage the editors to expand on this (I am not sure about whether it's appropriate, as well as the style, formatting, etc.) Mhym (talk) 22:06, 18 December 2009 (UTC)

David Eppstein edits: Ullman reference and Subgraph Isomorphism

David Eppstein wrote: Restore Ullman ref removed by Tim32 and re-remove subgraph isomorphism from see-also (already linked prominently from main article text) (15:52, 2 May 2010)

I would be very interested to know:

• 1) Why David Eppstein restored Ullman ref to paper about subgraph isomorphism?

• 2) Why David Eppstein re-remove subgraph isomorphism from see-also? It is very important point and a reader should not read entire article to find this one. Also, there are many links in the article and how a reader should know which link is very important and which link is minor?--Tim32 (talk) 16:12, 2 May 2010 (UTC)

(1) Because it's a relevant reference that you removed without providing any valid reasoning for the removal;

(2) WP:SEEALSO: "Links already integrated into the body of the text are generally not repeated in a 'See also' section".

—David Eppstein (talk) 16:39, 2 May 2010 (UTC)

1) it's a relevant reference for subgraph isomorphism, but not for graph isomorphism. See subgraph isomorphism, you will find this reference.

2) "However, whether a link belongs in the "See also" section is ultimately a matter of editorial judgment and common sense." WP:SEEALSO--Tim32 (talk) 17:42, 2 May 2010 (UTC)

It's primarily about subgraph isomorphism, but it also tests the algorithm on graph isomorphism problems. And in any case since we do mention subgraph isomorphism prominently in the text of the article, it's helpful to have a source to cite at that point. As for (2), yes, but the default is not to include it and I see no good reason to vary from the default in this case. By the way, I'm not the first editor to have made these edits here, only the most recent; the removal of the see-also link was done earlier by RobinK, Ullman has been cited by name and year for a long time in the article, and the actual citation was added recently by Dylan Thurston. So I don't know why you're attacking me in particular with the heading of this talk section. —David Eppstein (talk) 18:09, 2 May 2010 (UTC)

My 2¢:

1. Graph Isomorphism (GI) is a special case of subgraph isomorphism, so the reference is relevant.
2. (I could go either way on this point.) Since the link to subgraph isomorphism problem is placed prominently (i.e., in the lead, as opposed to obscurely embedded in some section), there's little need for it to be in the "See also".

Justin W Smith ^talk/_stalk 18:11, 2 May 2010 (UTC)

What makes Ullman's reference relevant is that it is cited in the first section, and therefore must appear in the references. --Robin (talk) 18:26, 2 May 2010 (UTC)

• "Graph Isomorphism (GI) is a special case of subgraph isomorphism" etc. - absurd or WP:OR. Let you write it in the article ;-) Is Graph a special case of subgraph? :-))) --Tim32 (talk) 19:59, 2 May 2010 (UTC)

Specifically, graph isomorphism is the special case of subgraph isomorphism in which the subgraph to be checked for being an isomorph has the same number of vertices and edges as the other graph in which it is to be embedded. How can you publish papers in this subject and not see this? As for being original research, the Ullman 1976 paper that you so dislike is a perfectly good source for this statement. —David Eppstein (talk) 20:04, 2 May 2010 (UTC)

Indeed, a graph is always its own subgraph. This isn't absurd or WP:OR, it's just by definition. --Robin (talk) 20:09, 2 May 2010 (UTC)

Dear David, Dear Robin,

I very like the paper by Ullman, but your statements is demagogy. I sincerely do not understand, why do you need this ref here, when special article about subgraph isomorphism exists. It seems, if I ask somebody to add any random ref, and I will remove it, you will restore it, only because it had been removed by me ;-)--Tim32 (talk) 20:25, 2 May 2010 (UTC)

PS If "graph isomorphism is the special case of subgraph isomorphism" only, then would you like to combine this article with subgraph isomorphism? ;) --Tim32 (talk) 20:44, 2 May 2010 (UTC)

PPS How can you publish papers in this subject, David? --Tim32 (talk) 20:47, 2 May 2010 (UTC)

Ok, per WP:BAIT I'm going to stop responding to you here. —David Eppstein (talk) 20:49, 2 May 2010 (UTC)

@Tim32, did you even bother to read the lead section of this article? It says,

"A generalization of the problem, the subgraph isomorphism problem, ..."

(I'm not sure why I'm even bothering to reply.) Justin W Smith ^talk/_stalk 21:14, 2 May 2010 (UTC)

• Please, stop your personal attack here! David Eppstein, I only repeated your words. Someone has a right to use devil's advocate position in discussion. I read the statement "A generalization of the problem, the subgraph isomorphism problem, ..." and I am agree with it. I only want to say that Ullman ref is not necessary here, there is the link to subgraph isomorphism article, where the ref is used. Otherwise somebody may copy another refs from subgraph isomorphism article and from graph automorphism problem article to this article. Note again, I do not say that I dislike Ullman's paper, these are words by David Eppstein about me. The second point: graph automorphism problem link is already integrated into the body of the text, but this link is copied in "See also" section. Why subgraph isomorphism link should not be added to "See also" too?--Tim32 (talk) 07:18, 3 May 2010 (UTC)

PS Also, "graph canonization" link is already integrated into the body of the text, but this link is copied in "See also" section. --Tim32 (talk) 09:25, 3 May 2010 (UTC)

Other problem of Garey and Johnson

The article mentions that graph isomorphism is one of only two problems in Garey and Johnson whose complexity is still unknown. It would be an interesting addition if the article mentions what the other one is. (I don't know the answer, though. Factorization, maybe?) -- Walt Pohl (talk) 15:08, 27 September 2010 (UTC)

Yes, integer factorization. I added a link. Dcoetzee 08:10, 28 September 2010 (UTC)

Actually, that is not the problem in G&J. The problem in the book is primality/compositeness testing, not factoring. And that problem has been famously solved.

There doesn't seem to be any point to mentioning the (partial) solution to minimum-weight triangulation here. I've moved the citation to Computers and Intractability. Also note that MWT wasn't completely solved as had been incorrectly stated here: the problem was proved to be NP-hard, but it is unknown whether it is in NP in the first place. I believe it is worthlessly distracting to this article to include such a fine point. I've put the precise statement in the C&I article.

I also deleted the footnote in the lede to best algorithms, as it is cited later in context. Choor monster (talk) 16:20, 21 August 2015 (UTC)

Babai

László Babai announced a quasipolynomial algorithm for graph isomorphism [3]. Not even a preprint has been published yet, but it’s something to keep an eye on.—Emil J. 13:39, 4 November 2015 (UTC)

Yes, but let's hold off mentioning it in the article until some detail emerges. —David Eppstein (talk) 16:35, 4 November 2015 (UTC)

Seems verifiable and fitting to say that he's announced a talk about a new algorithm. – SJ + 22:02, 5 November 2015 (UTC)

The only actual verifiable information we have is the talk title. Everything beyond that is rumor. And the title doesn't unambiguously tell us that he has a worst-case quasinomial time bound on graph isomorphism for all graphs; it's much shorter than that, and strongly suggests that he has such an algorithm, but could be interpreted in other ways. What's the rush? Why not wait until we actually know something? —David Eppstein (talk) 22:38, 5 November 2015 (UTC)

Wasn't mention here on WP of Mochizuki's claim, complete with preprints, to have proven the abc conjecture delayed for quite some time? Choor monster (talk) 14:01, 6 November 2015 (UTC)

Maybe I need to brush up on my wikipedia policies, but isn't mention in [mainstream print](http://news.sciencemag.org/math/2015/11/mathematician-claims-breakthrough-complexity-theory) news sufficient for [notability](https://en.wikipedia.org/wiki/Wikipedia:Notability)? People reading such articles might head over to this page and think it's outdated. 2001:981:2E0D:1:DC0:BBFB:801E:711E (talk) 06:35, 12 November 2015 (UTC)

Also, [4] — Preceding unsigned comment added by 193.224.79.1 (talk) 06:24, 14 November 2015 (UTC)

For the record, you cited the incorrect policy/guideline: we need verification, not notability. You also bizarrely posed it as some kind of contradiction to statements made before its publication. As it is, we now have RS verification that a proof is claimed. (Coincidentally, if my memory is correct, it was Science publishing on the abc conjecture buzz that tipped the scales to inclusion.) Choor monster (talk) 14:33, 15 November 2015 (UTC)

You misunderstand. What I'm suggesting is that the page include the news that a proof has been claimed for a new bound. That's news, and that requires notability. If we want to claim that the bound exists, we need verification, but that's for later. I mention people coming to this page, because when Science and Nature mention the news but Wikipedia doesn't, it looks like Wikipedia is out of date. 2001:981:2E0D:1:4C4E:B5F6:2E91:4908 (talk)

You are not making much sense, on several levels. I explicitly referred to the claim, and recommended inclusion, because we do have RS that a claim has been made for a proof, and that suffices for verification, and thus inclusion in a relevant article. Notability is never necessary for individual items in an article. Verification (along with UNDUE, BLP, and the like) is the lower bar needed for individual points within an article, whose overall topic is what is required to pass notability.

Regarding WP seeming out of date. Of course! WP follows, it does not lead. I encourage you or anyone else to update the article regarding the announced claim. See abc conjecture for an example of how we do that, regarding wording, credit, and sourcing. If and when it becomes clear that the proof is accepted as genuine, for example if Gil Kalai blogs that it is so, then we can revise the wording appropriately. Similarly, in the unfortunate situation that a major hole is discovered and blogged about by a prominent mathematician, that too should be included. Unlike the recent Dr Enoch and the Riemann Hypothesis flapdoodle, which was simply pointless from the get-go, Babai's work is inherently interesting, even when it doesn't work as claimed. Choor monster (talk) 15:13, 22 November 2015 (UTC)