Yeah, I'd be curious what the opinions of other researchers in this area are. There have been a number of debunked polynomial time algorithms for GI, so it's one of those things people are always skeptical of; but that of course doesn't mean this one is wrong too.
The author of the paper recently posted a blog comment in which he says he submitted to a few journals, and complains that "referees did not find any fatal error in my proof, but all the journals rejected this paper": http://rjlipton.wordpress.com/2009/05/04/an-approach-to-grap...
I'd take that as evidence that the referees at least didn't think it was a successful proof. The comment is attached to an old blog post about the problem from a well-known theoretical computer scientist (R.J. Lipton), but since it was posted about a year after the initial post, it hasn't gotten any replies.
This makes me nervous:
Further, without loss of generality of the task, we will consider undirected
connected graphs without loops.
Tree isomorphism is polynomial. It's not obvious to me how you cut the loops out of two graphs and ensure you end up with similar trees. Quick scan didn't show that in the paper. I guess i'll have to read in more detail after dinner.
tl;dr:
Graph isomorphism recognition is an old and well-known problem that is in NP. It was not known whether it was NP-complete or in P, but this paper suggests that it is in P. This is kind of Big, assuming the paper's correct.
This would be big news if true (though not P=NP-big; graph isomorphism is an apparently-hard problem that isn't known to be NP-hard).
From a cursory glance, it doesn't look terribly promising, but I haven't made a serious attempt to see what he's doing and how it might work. Examples of not-terribly-promising things:
1. He proves what he calls "Assertion 1", then says that it "suggests" some other propositions that he calls "Conclusion 1", "Conclusion 2", "Conclusion 3". He doesn't offer any proofs of these; they don't seem to be obvious consequences of Assertion 1; they don't even seem very likely to be true. In particular, Assertion 1 has the form "if graphs G and G' are isomorphic, then [linear algebra stuff]" and Conclusion 2 (which he uses later) has the form "if [linear algebra stuff] then graphs G and G' are isomorphic".
2. He then defines this thing he calls a W-matrix, which seems like it basically encodes for a given vertex of a given graph which other vertices are at any given distance from it. He then appears to claim -- I'm not quite sure, because his notation is eccentric and it's late at night -- that equality of W-matrices is basically the same thing as similarity of vertices (i.e., whether some graph automorphism carries one to the other), and that doesn't look right to me.
I repeat that I haven't looked at this carefully, and I'm not an expert in the field anyway. But it's not compelling enough to make me want to spend much more time on it; I expect that if it turns out to be valid someone smarter than me will check it over and let the world know :-).
Anyone can post to the ArXiv. So now wait a few weeks. One test: does his algorithm work for bipartite graphs? Another test: his algorithm uses real numbers. This is sketchy, as real numbers can't actually be represented in a computer.
The paper is pretty poorly written for two reasons: English is clearly not this guy's first language (no crime there, as it is said that the language of science is "heavily accented english") but he is also using a little too much handwaving for my comfort. This is a pretty math-heavy result, and this is not an airtight proof in any sense.
Basically: I agree with everything you said about it not being compelling enough for me to spend more time with it.
Fun fact so that I'll say more than "I agree": if GI is in P, the the polynomial hierarchy collapses to a level that I forget, and if GI is NPC it collapses to a PI_2! Neat!
As an aside, theres some really beautiful results in graph theory that are only nicely expressible if you use linear algebra (aka spectral graph theory).
That being said, there are several problems with the paper:
1) it seems to implicitly assuming (without realizing it) that any two graphs it is considering at k-regular for some unspecified k. This is barely more general than assuming that graphs are planar, so itd be easy to have pretty reasonable algorithm for such a case (i'm pretty sure there are bunches in the research literature).
Also, it doesn't really seem to be addressing integrality of the linear programs, which i think is kinda key when using linear programs for combinatorics!
I can't help comparing this to the extreme absence of self-promotion in the most prominent example of somebody doing this who turned out to be the real thing (Perelman).
Yeah. But you've got to be careful; lots of people dismissed Louis de Branges' claim to have proved the Bieberbach conjecture because he also had a long history of self-promotion (and, indeed, of claiming to have proved things when his proofs really had holes). But he really did prove the Bieberbach conjecture.
Then again, he also keeps claiming to have proved the Riemann hypothesis and no one believes him :-).
%!PS-Adobe-2.0
%%Creator: dvipsk 5.55a Copyright 1986, 1994 Radical Eye Software
%%Title: linear.dvi
%%Pages: 31
%%PageOrder: Ascend
%%BoundingBox: 0 0 612 792
%%EndComments
%DVIPSCommandLine: dvips linear
%DVIPSParameters: dpi=300, compressed, comments removed
%DVIPSSource: TeX output 1994.09.10:1557
%%BeginProcSet: texc.pro
/TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N
/X{S N}B /TR{translate}N /isls false N /vsize 11 72 mul N /hsize 8.5 72
mul N /landplus90{false}def /@rigin{isls{[0 landplus90{1 -1}{-1 1}
ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale
isls{landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div
hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul
TR[matrix currentmatrix{dup dup round sub abs 0.00001 lt{round}if}
forall round exch round exch]setmatrix}N /@landscape{/isls true N}B
/@manualfeed{statusdict /manualfeed true put}B /@copies{/#copies X}B
/FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{
/nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N
string /base X array /BitMaps X /BuildChar{CharBuilder}N /Encoding IE N
end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{
/sf 1 N /fntrx FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0]
N df-tail}B /E{pop nn dup definefont setfont}B /ch-width{ch-data dup
length 5 sub get}B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{
128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub
get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data
dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N
/rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup
/base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx
0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff
setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff
.1 sub]/id ch-image N /rw ch-width 7 add 8 idiv string N /rc 0 N /gp 0 N
/cp 0 N{rc 0 ne{rc 1 sub /rc X rw}{G}ifelse}imagemask restore}B /G{{id
gp get /gp gp 1 add N dup 18 mod S 18 idiv pl S get exec}loop}B /adv{cp
add /cp X}B /chg{rw cp id gp 4 index getinterval putinterval dup gp add
/gp X adv}B /nd{/cp 0 N rw exit}B /lsh{rw cp 2 copy get dup 0 eq{pop 1}{
dup 255 eq{pop 254}{dup dup add 255 and S 1 and or}ifelse}ifelse put 1
adv}B /rsh{rw cp 2 copy get dup 0 eq{pop 128}{dup 255 eq{pop 127}{dup 2
idiv S 128 and or}ifelse}ifelse put 1 adv}B /clr{rw cp 2 index string
putinterval adv}B /set{rw cp fillstr 0 4 index getinterval putinterval
adv}B /fillstr 18 string 0 1 17{2 copy 255 put pop}for N /pl[{adv 1 chg}
{adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{
adv rsh nd}{1 add adv}{/rc X nd}{1 add set}{1 add clr}{adv 2 chg}{adv 2
chg nd}{pop nd}]dup{bind pop}forall N /D{/cc X dup type /stringtype ne{]
}if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup
length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N}B /I{
cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin
0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul
add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore showpage
userdict /eop-hook known{eop-hook}if}N /@start{userdict /start-hook
known{start-hook}if pop /VResolution X /Resolution X 1000 div /DVImag X
/IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for
65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0
0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V
{}B /RV statusdict begin /product where{pop product dup length 7 ge{0 7
getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false}
ifelse}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale rulex ruley false
RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR rulex ruley scale 1 1
false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave newpath transform
round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg
rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail...
%!PS-Adobe-2.0
%%Creator: dvipsk 5.55a Copyright 1986, 1994 Radical Eye Software
%%Title: linear.dvi
%%Pages: 31
%%PageOrder: Ascend
%%BoundingBox: 0 0 612 792
%%EndComments
%DVIPSCommandLine: dvips linear
%DVIPSParameters: dpi=300, compressed, comments removed
%DVIPSSource: TeX output 1994.09.10:1557
%%BeginProcSet: texc.pro
/TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N
/X{S N}B /TR{translate}N /isls false N /vsize 11 72 mul N /hsize 8.5 72
mul N /landplus90{false}def /@rigin{isls{[0 landplus90{1 -1}{-1 1}
ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale
isls{landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div
hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul
TR[matrix currentmatrix{dup dup round sub abs 0.00001 lt{round}if}
forall round exch round exch]setmatrix}N /@landscape{/isls true N}B
/@manualfeed{statusdict /manualfeed true put}B /@copies{/#copies X}B
/FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{
/nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N
string /base X array /BitMaps X /BuildChar{CharBuilder}N /Encoding IE N
end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{
/sf 1 N /fntrx FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0]
N df-tail}B /E{pop nn dup definefont setfont}B /ch-width{ch-data dup
length 5 sub get}B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{
128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub
get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data
dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N
/rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup
/base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx
0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff
setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff
.1 sub]/id ch-image N /rw ch-width 7 add 8 idiv string N /rc 0 N /gp 0 N
/cp 0 N{rc 0 ne{rc 1 sub /rc X rw}{G}ifelse}imagemask restore}B /G{{id
gp get /gp gp 1 add N dup 18 mod S 18 idiv pl S get exec}loop}B /adv{cp
add /cp X}B /chg{rw cp id gp 4 index getinterval putinterval dup gp add
/gp X adv}B /nd{/cp 0 N rw exit}B /lsh{rw cp 2 copy get dup 0 eq{pop 1}{
dup 255 eq{pop 254}{dup dup add 255 and S 1 and or}ifelse}ifelse put 1
adv}B /rsh{rw cp 2 copy get dup 0 eq{pop 128}{dup 255 eq{pop 127}{dup 2
idiv S 128 and or}ifelse}ifelse put 1 adv}B /clr{rw cp 2 index string
putinterval adv}B /set{rw cp fillstr 0 4 index getinterval putinterval
adv}B /fillstr 18 string 0 1 17{2 copy 255 put pop}for N /pl[{adv 1 chg}
{adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{
adv rsh nd}{1 add adv}{/rc X nd}{1 add set}{1 add clr}{adv 2 chg}{adv 2
chg nd}{pop nd}]dup{bind pop}forall N /D{/cc X dup type /stringtype ne{]
}if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup
length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N}B /I{
cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin
0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul
add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore showpage
userdict /eop-hook known{eop-hook}if}N /@start{userdict /start-hook
known{start-hook}if pop /VResolution X /Resolution X 1000 div /DVImag X
/IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for
65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0
0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V
{}B /RV statusdict begin /product where{pop product dup length 7 ge{0 7
getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false}
ifelse}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale rulex ruley false
RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR rulex ruley scale 1 1
false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave newpath transform
round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg
rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail...
One thing particularly interesting about this is that Graph Isomorphism is in a hypothetical category of problems sometimes dubbed "NP-intermediate": they are believed to be hard, but nobody has proven they're NP-complete. Linear programming used to be one of these, but was proven (rather brilliantly) to be in P by Leonid Khachiyan in 1979.
Notably, as far as I know, it hasn't been proven that NP-intermediate even exists. It's quite possible that all problems believed to be in that category are actually either P or NP-complete. If this proof is on the right track, this possibility may be all the more likely.
Hi,
I’m Michael Trofimov, the author of this preprint.Thank you for your interest, you are welcome to ask your questions. More info about me you can find, for example, in Intel site: http://software.intel.com/sites/blackbelt/hall_of_fame.php
(see Top Community Masterminds section). Is it self-promotion? ;-)
Yes, I am not native English speaker, so I would be very thankful if somebody will mark unclear statements in the paper and will suggest his/her version. Very important: this is preprint only! It is not final result, the investigation is under the progress. During discussion in other web-sites and via emails: one minor bug in the proof and one bug in program had been found. The program bug was fixed, also some time later I will upload the second version of the paper to arXiv.
22 comments
[ 3.0 ms ] story [ 38.3 ms ] threadBut it's not clear how much of the paper they looked at and whether they think it's correct.
The author of the paper recently posted a blog comment in which he says he submitted to a few journals, and complains that "referees did not find any fatal error in my proof, but all the journals rejected this paper": http://rjlipton.wordpress.com/2009/05/04/an-approach-to-grap...
I'd take that as evidence that the referees at least didn't think it was a successful proof. The comment is attached to an old blog post about the problem from a well-known theoretical computer scientist (R.J. Lipton), but since it was posted about a year after the initial post, it hasn't gotten any replies.
Tree isomorphism is polynomial. It's not obvious to me how you cut the loops out of two graphs and ensure you end up with similar trees. Quick scan didn't show that in the paper. I guess i'll have to read in more detail after dinner.
That's fine because you can ignore them until the end, and then just check your vertices for any loops, in O(n) time.
tl;dr: Graph isomorphism recognition is an old and well-known problem that is in NP. It was not known whether it was NP-complete or in P, but this paper suggests that it is in P. This is kind of Big, assuming the paper's correct.
From a cursory glance, it doesn't look terribly promising, but I haven't made a serious attempt to see what he's doing and how it might work. Examples of not-terribly-promising things:
1. He proves what he calls "Assertion 1", then says that it "suggests" some other propositions that he calls "Conclusion 1", "Conclusion 2", "Conclusion 3". He doesn't offer any proofs of these; they don't seem to be obvious consequences of Assertion 1; they don't even seem very likely to be true. In particular, Assertion 1 has the form "if graphs G and G' are isomorphic, then [linear algebra stuff]" and Conclusion 2 (which he uses later) has the form "if [linear algebra stuff] then graphs G and G' are isomorphic".
2. He then defines this thing he calls a W-matrix, which seems like it basically encodes for a given vertex of a given graph which other vertices are at any given distance from it. He then appears to claim -- I'm not quite sure, because his notation is eccentric and it's late at night -- that equality of W-matrices is basically the same thing as similarity of vertices (i.e., whether some graph automorphism carries one to the other), and that doesn't look right to me.
I repeat that I haven't looked at this carefully, and I'm not an expert in the field anyway. But it's not compelling enough to make me want to spend much more time on it; I expect that if it turns out to be valid someone smarter than me will check it over and let the world know :-).
The paper is pretty poorly written for two reasons: English is clearly not this guy's first language (no crime there, as it is said that the language of science is "heavily accented english") but he is also using a little too much handwaving for my comfort. This is a pretty math-heavy result, and this is not an airtight proof in any sense.
Basically: I agree with everything you said about it not being compelling enough for me to spend more time with it.
Fun fact so that I'll say more than "I agree": if GI is in P, the the polynomial hierarchy collapses to a level that I forget, and if GI is NPC it collapses to a PI_2! Neat!
Please, download the program and test any graph you like ;)
That being said, there are several problems with the paper: 1) it seems to implicitly assuming (without realizing it) that any two graphs it is considering at k-regular for some unspecified k. This is barely more general than assuming that graphs are planar, so itd be easy to have pretty reasonable algorithm for such a case (i'm pretty sure there are bunches in the research literature).
Also, it doesn't really seem to be addressing integrality of the linear programs, which i think is kinda key when using linear programs for combinatorics!
They do seem! In a few words, this fragment was cited from peer reviewed article http://dx.doi.org/10.1007/s11172-006-0105-6 .
> how it might work
Please, download the program and see...
Then again, he also keeps claiming to have proved the Riemann hypothesis and no one believes him :-).
Notably, as far as I know, it hasn't been proven that NP-intermediate even exists. It's quite possible that all problems believed to be in that category are actually either P or NP-complete. If this proof is on the right track, this possibility may be all the more likely.
Yes, I am not native English speaker, so I would be very thankful if somebody will mark unclear statements in the paper and will suggest his/her version. Very important: this is preprint only! It is not final result, the investigation is under the progress. During discussion in other web-sites and via emails: one minor bug in the proof and one bug in program had been found. The program bug was fixed, also some time later I will upload the second version of the paper to arXiv.
All the best, -- Michael.