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

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.