replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/

Given a group $$G$$ acting on a set $$X$$ with a total order $$\leq$$ and an $$x\in X$$, what is the most efficient algorithm for deciding whether or not x is the least element in its orbit, in other words, deciding if $$min(Gx) = x$$?

My motivation comes from SMT solving where there has been some interest in automatically breaking symmetries. Adding symmetry breaking predicates often result in a large clause set therefore I am interested in the possibility of handling this as a lazy theory propagation.

The above description is perhaps too general, and as noted by sidsid, NP-hard. A possible simpler task is, given a group of permutations of strings of length $$n$$ encoded as a set of generators and a string $$x$$ of length $$n$$. What is the most efficient algorithm for deciding if that string is the lexicographically smallest in its orbit?

edited tags
Suresh Venkat
• 31.6k
• 4
• 90
• 267
Given a group $$G$$ acting on a set $$X$$ with a total order $$\leq$$ and an $$x\in X$$, what is the most efficient algorithm for deciding whether or not x is the least element in its orbit, in other words, deciding if $$min(Gx) = x$$?
The above description is perhaps too general, and as noted by sid, NP-hard. A possible simpler task is, given a group of permutations of strings of length $$n$$ encoded as a set of generators and a string $$x$$ of length $$n$$. What is the most efficient algorithm for deciding if that string is the lexicographically smallest in its orbit?