# Timeline for What is the most efficient algorithm for deciding if an element is the least in its orbit?

### Current License: CC BY-SA 3.0

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 @JɛﬀE , 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 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 @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 timeline score: 9
Dec 8 '11 at 15:42 history edited
edited tags
Dec 8 '11 at 14:21 history tweeted
Dec 8 '11 at 13:43 history edited
Dec 8 '11 at 13:14 comment If $G$ and $X$ are presented as value oracles, this requires enumerating $G$.
Dec 8 '11 at 10:18 comment 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.