patternMajor
Has the graph isomorphism problem been solved?
Viewed 0 times
problemthegraphbeenhassolvedisomorphism
Problem
Wikipedia's graph isomorphism problem page would seem to indicate that, no, it has not been solved. However, a friend of mine pointed out A Polynomial Time Algorithm for Graph Isomorphism . I am not sophisticated enough to follow the reasoning in the paper.
I do have my own very rough attempt at a polynomial time algorithm without anything like proof, but I'd like to know whether or not this problem has been successfully tackled before proceeding.
So, is the graph isomorphism problem solved?
I do have my own very rough attempt at a polynomial time algorithm without anything like proof, but I'd like to know whether or not this problem has been successfully tackled before proceeding.
So, is the graph isomorphism problem solved?
Solution
No. That paper appears to be flawed. The flaw was explained in a comment by Tracy Hall on MathOverflow. A follow-up comment claims that the author later realized there is a flaw in his algorithm.
As Yuval explains, it is not uncommon to see attempts from amateurs to solve these problems; they tend to be flawed. When it comes to results on famous open problems (e.g., P vs NP, graph isomorphism, etc.), I recommend looking to published literature in reputable peer-reviewed conferences and journals -- peer review is not perfect, but peer-reviewed papers have a much higher likelihood of being correct.
As Yuval explains, it is not uncommon to see attempts from amateurs to solve these problems; they tend to be flawed. When it comes to results on famous open problems (e.g., P vs NP, graph isomorphism, etc.), I recommend looking to published literature in reputable peer-reviewed conferences and journals -- peer review is not perfect, but peer-reviewed papers have a much higher likelihood of being correct.
Context
StackExchange Computer Science Q#35260, answer score: 24
Revisions (0)
No revisions yet.