4 ms·
An Annoying Open Problem
- dr_rezzy 15y agoZeke was my theory and algorithms prof in college. Kind of hard to wrap your head around these sort of problems.
- gms 15y agoI was really surprised to learn that this is still an open problem.
- veyron 15y agoThere are a lot of simple heuristics (like score sequences) which get close but can't handle a lot of annoying corner cases.
- tgflynn 15y agoDoes anyone know of any good test cases for GI ? I have a GI algorithm or heuristic but I don't know how to evaluate it compared to the current algorithms.
- mckoss 15y agoNaive question. Can the cycle structure of two groups be used to optimize comparison, just as the Poles used in WWII to catalog all the possible rotor configurations of an Enigma machine?
- anonymoushn 15y agoYes, but this won't help you with the general case.
- anonymoushn 15y agoIs graph isomorphism known to be in P or not in P? The article seems to suggest that it is known not to be in P, but I haven't heard anything about this.
- cperciva 15y agoGraph isomorphism is one of the two big problems which are not known to be in P and also not known to be NP-complete. (Integer factorization is the other.)
- veyron 15y agoLadner's theorem established that if NP != P, then there exists "NP-easy" problems which are in NP but not in P. It has been shown that if P != NP, then GI is in that valley.
- bdhe 15y agoIt has been shown that if P != NP, then GI is in that valley. Could you point to a reference? Is this true even if P != NP, but NP = coNP?
- thesteamboat 15y agoThis pdf (http://www.cs.princeton.edu/theory/complexity/ipchap.pdf http://www.cs.princeton.edu/theory/complexity/ipchap.pdf) which is a draft chapter from a book by Arora and Barak, shows that if GI is NP-complete, then the polynomial hierarchy collapses to the second level. Collapse to the first level is when NP=coNP. So this is slightly weaker even than that.
- bdr 15y agoWikipedia disagrees: http://en.wikipedia.org/wiki/NP-intermediate http://en.wikipedia.org/wiki/NP-intermediate "In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate" "Under the assumption that P ≠ NP, Ladner explicitly constructs a problem in NPI, however this problem is artificial and otherwise uninteresting. It is an open question whether any "natural" problem has the same property."
- jmmcd 15y agoIs there a layman-readable proof or proof-sketch of the reduction from Group Isomorphism to Graph Isomorphism? Is the method constructive, so that every group reduces to a corresponding graph in an understandable way? I have a somewhat cranky reason for asking. In evolutionary algorithms, a mutation operator is one which transforms an existing genome into a single new one. One can study the behaviour of an operator by drawing an edge from old to new genomes, for every possible genome, and studying the resulting graph. A crossover operator takes two parent genomes to produce a new one. No-one really has a satisfactory method of studying crossover analogous to that for mutation. The problem is we need edges to lead from pairs of nodes to single nodes. So kind of like hyperedges but not exactly. I've been hoping for a while that there is an answer in existing graph theory. Crossover is also kind of like a group operation, but again not exactly. So that's why the idea of mapping a group to a graph is interesting.
- tgflynn 15y agoYou might want to look at the definition of Cayley graphs : http://en.m.wikipedia.org/wiki/Cayley_graph http://en.m.wikipedia.org/wiki/Cayley_graph