14 events
when toggle format what by license comment
Apr 13 '17 at 12:32 history edited CommunityBot
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
Dec 12 '11 at 14:07 comment added HaskellElephant @JɛffE , the specific case that I am interested is the second description I give, the first description is just a more general case, any encoding that is interesting is fine. And yes, I am only interested in finite groups.
Dec 12 '11 at 12:06 comment added Jeffε Define "Given a group G..."! What, precisely, are we "given"? An explicit multiplication table? A multiplication oracle? A generator-relator presentation? A matrix representation? May/must the group be finite? Discrete?
Dec 10 '11 at 20:01 comment added Joshua Grochow @HaskellElephant: if you're interested in practical algorithms, maybe you can use techniques from Brendan McKay's program nauty (cs.anu.edu.au/~bdm/nauty), which is widely cited as the best current graph isomorphism solver in practice, though it is known to have exponential worst-case complexity.
Dec 10 '11 at 17:56 answer Joshua Grochow timeline score: 9
Dec 8 '11 at 15:42 history edited Suresh Venkat
edited tags
Dec 8 '11 at 14:21 history tweeted twitter.com/#!/StackCSTheory/status/144783776256499712
Dec 8 '11 at 13:43 history edited HaskellElephant CC BY-SA 3.0
added 402 characters in body
Dec 8 '11 at 13:14 comment added David Harris If $G$ and $X$ are presented as value oracles, this requires enumerating $G$.
Dec 8 '11 at 12:45 comment added HaskellElephant @PeterShor, yes, in fact for my purpose, any canonical form will do.
Dec 8 '11 at 12:14 comment added Peter Shor Although if you use a different criterion for minimum, it's polynomial here: it's easy to find the lexicographically smallest tour (at least if you assume all the edges have different labels; otherwise, it's still NP-hard).
Dec 8 '11 at 10:46 comment added HaskellElephant @Sid, yes I am only interested in the case where X is finite, and I hadn't thought of it but it is certainly NP-hard. I guess there might still be a possibility of an efficient monte carlo algorithm.
Dec 8 '11 at 10:18 comment added Opt I presume you're talking about finite sets X? I think deciding this is NP-hard. Let $X=\{c_1,\dots,c_n\}$ be a tour of a set of cities in the Traveling Salesman problem with $c_1 \rightarrow c_2 \dots$. Let the group $G$ be the symmetric group $S_n$. Then the orbit is all possible tours and proving that one of them is minimum is NP-hard.
Dec 8 '11 at 10:04 history asked HaskellElephant CC BY-SA 3.0