8
$\begingroup$

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 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?

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ 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. $\endgroup$
    – Opt
    Dec 8, 2011 at 10:18
  • $\begingroup$ @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. $\endgroup$
    – HaskellElephant
    Dec 8, 2011 at 10:46
  • 1
    $\begingroup$ 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). $\endgroup$
    – Peter Shor
    Dec 8, 2011 at 12:14
  • $\begingroup$ @PeterShor, yes, in fact for my purpose, any canonical form will do. $\endgroup$
    – HaskellElephant
    Dec 8, 2011 at 12:45
  • $\begingroup$ If $G$ and $X$ are presented as value oracles, this requires enumerating $G$. $\endgroup$
    – David Harris
    Dec 8, 2011 at 13:14

1 Answer 1

Reset to default
9
$\begingroup$

For general equivalence relations, not those arising from permutation group actions, even finding lexicographically least is still "too" general. Finding the lexicographically smallest element in an equivalence class can be $NP$-hard (in fact, $P^{NP}$-hard) - even if the relationship has a polynomial-time canonical form [1].

However, for permutation group orbit problems as you describe, deciding whether two points lie in the same orbit is not likely to be $NP$-hard: it is in $NP \cap coAM$, and hence not $NP$-hard unless the polynomial hierarchy collapses to the second level.

A canonical form for graph isomorphism is also a special case of the second problem you state. The best known canonical form for graph isomorphism runs in time $2^{\tilde{O}(\sqrt{n})}$ [2].

Since you said in the comments that any canonical form will do, you might also be interested in my paper with Lance Fortnow [3]: in its currently generality, I think your question is related to our results. We show that if every equivalence relation decidable in $P$ has a canonical form in $P$, then "bad" consequences result, such as $NP = UP = RP$, which in particular implies that the polynomial hierarchy collapses down to $BPP$. On the other hand, the equivalence relations you're interested in may not be in $P$, but this result suggests that even if it lies in a higher complexity class other hard problems may still stand in your way.

So I think if you want some better upper bounds you really need the problem to be more specific.

[1] Andreas Blass and Yuri Gurevich. Equivalence relations, invariants, and normal forms. SIAM J. Comput. 13:4 (1984), 24-42.

[2] László Babai and Eugene M. Luks. Canonical labelings of graphs. STOC 1983, 171-183.

[3] Lance Fortnow and Joshua A. Grochow. Complexity classes of equivalence problems revisited. Inform. and Comput. 209:4 (2011), 748-763. Also available as arXiv:0907.4775v2.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Does GI in poly time imply $PEq=CF$ in your paper? What would imply such a result (any complete problems) and what would separate? $\endgroup$
    – Turbo
    Dec 7, 2015 at 18:54
  • 1
    $\begingroup$ Not as far as I know. At best it would imply that any problem of combinatorial isomorphism is in Ker(FP); one issue is that a canonical form for a graph need not yield a canonical form for the structure you started with; the other issue is that combinatorial isomorphism isn't necessarily PEq-complete. We asked whether there were PEq-complete problems; Finkelstein and Hescott showed CEq-complete problems for C higher up in PH, but left open the question of the existence of PEq-complete problem. $\endgroup$
    – Joshua Grochow
    Dec 7, 2015 at 20:19
  • $\begingroup$ would it be possible that existence of a complete problem in PEq implies PH collapses to some level? $\endgroup$
    – Turbo
    Dec 7, 2015 at 20:52
  • $\begingroup$ @Turbo: Sure, though it seems a little unlikely to me. Do you know of any example where the existence of a complete problem for some class implies PH collapses? (Other than PH-complete problems.) I think it's likely that either (a) PEq-complete problems exist (and don't contradict major conjectures), we just haven't figured out how to construct them, or (b) there are oracles going both ways on the existence of PEq-complete problems. (b) seems more likely to me - by analogy with BPP - because PEq is essentially a semantic class. $\endgroup$
    – Joshua Grochow
    Dec 7, 2015 at 22:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.