Re:Graph Isomorphism Strikes Back
by baq on Friday January 06, 2017 @06:59AM
(#13335648)
not disagreeing with you at all, more like expanding your comment.
for some definitions of 'almost', especially the vague human ones, there are very surprising results (well, not for people with CS education, but for the other ones). e.g. 2-SAT vs 3-SAT, hamiltonian path (visit all nodes on a graph) vs eulerian path (visit all edges), shortest path vs longest path, etc. like i said, the 'almost' is debatable, but for the untrained eye the problems are very similar.
for some definitions of 'almost', especially the vague human ones, there are very surprising results (well, not for people with CS education, but for the other ones). e.g. 2-SAT vs 3-SAT, hamiltonian path (visit all nodes on a graph) vs eulerian path (visit all edges), shortest path vs longest path, etc. like i said, the 'almost' is debatable, but for the untrained eye the problems are very similar.