Computational complexity of sizes and number of orbits of a group acting on a set

Question

I'm interested in the relation between the computational complexity of counting orbits and counting elements in orbits for groups acting on sets. More formally:

Assume that $X_n$ is a infinite sequence of finite sets index by $n\in\mathbb{N}$. Assume that $G$ is a group with a finite set of generators. Furthermore assume that a group action of $G$ is defined on each set $X_n$ and that this action can be efficiently computed given an element of $G$ and an element of $X$.

Consider the following two problems:

Problem 1 (counting orbits): Input: $n$

Given $n$, decide the number of orbits of $G$ acting on $X_n$, i.e. compute the size $|X_n/G|=|\{\{g\cdot x:g\in G\}:x\in X_n\}|$.

Problem 2 (size of orbit): Input: $x\in X_n$

Given $x\in X_n$, decide the number of elements in the orbit of $G$ acting on $X_n$ containing x, i.e. compute the size $|\{g\cdot x:g\in G\}|$.

Does $\#P$-Completeness of Problem 2 imply $\#P$-Completeness/Hardness of Problem 1?

Note that $\#P$-Completeness of Problem 2 implies that the size of $X_n$ must scale super-polynomially with $n$.

Note: I've asked a similar question on StackExchange/Mathematics, however after two weeks and only an unrelated answer I thought I'd also ask the same question here.

Answer 1

Since group actions on set can be quite wild (little restrictions on compatibility) I am not too aware of any relation or even chance of finding such a reltaion, however, if you have something like a free action or something similar, this should considerably help to actually make your problems equivalent (since for example for a free action all orbits are in bijection). I hope that helps!

Answer 2

[Too long for a comment. Not a definitive answer, but maybe as close as we're likely to get.]

I'm assuming here, since you talk about $X_n$ being potentially exponentially large, that we may think of $X_n$ as being a subset of binary strings whose length is at most polynomial in $n$, and that the action of each generator of $G$ is efficiently computable in $n$, given such a binary string. (Probably the use of binary strings isn't key, but it seems to be consistent with your intention, and to clear up some of the questions in the comments.)

First, an example: Graph Isomorphism. $X_n$ is the set of $n$-vertex graphs. It's more natural in this setting to allow the group $G_n$ to vary with $n$, and to be $S_n$, but the way you've set it up I suppose I'd say $G=F_2$ is the free group on 2 generators, and the action of $G$ on $X_n$ is by permuting the $n$ vertices. (This is an action of $F_2$ since $S_n$ is generated by 2 elements.) Then computing orbit size is equivalent to computing $|Aut(x)|$, which - by a standard result - is poly-time equivalent to computing Graph Isomorphism. By Babai's result, this can be done in $n^{O(\log n)^2}$ time. On the other hand, exactly counting the number of isomorphism classes seems to be exponentially harder, though this is an interesting open question. Now, in this case, computing the orbit size seems to not be #P-hard, and it's unclear whether counting the number of graphs is (but that also seems a bit unlikely), so this example doesn't get at your question about #P.

This situation - computing orbit size seems easier than counting orbits - seems typical for most natural isomorphism problems I'm aware of (graph, group, finite ring, tensors over finite fields, algebras, etc.). This might suggest a positive answer to your question about #P-completeness, except that also for most natural isomorphism problems I'm aware of, neither orbit size nor counting orbits seems to be #P-complete.

More generally, I'm don't think I know of even a single #P-complete problem whose input is just one number $n$. This is related to some of the difficulty in answering Kalai's question about computing the number of isomorphism classes of graphs (see the comments there). You can start to see the difficulty if you think about trying to reduce #3SAT to a problem whose sole input is an integer $n$.

Answer 3

I assume that you are given a finite set $X=\{x_1,\ldots,x_m\}$ and a finite set of generators for $G$, say $g_1, \ldots, g_n$, which are permutations of $X$.

Then, for every $i$ and $j$, imagine a directed edge from $x_i$ to $g_j\cdot x_i$. This constructs a directed graph from the data. The orbits are the connected components. The size of this graph is quadratic in terms of the input. Either breadth-first search or depth-first search provides a linear time algorithm for finding these connected components. Not sure what assumptions you need to begin with to get close to $\# P$-complete. Do you have in mind some formulation of this problem where $X$ is infinite?