Determining what can be achieved by a permutation of elements of a noncommutative group

Question

Fix a finite group $G$. I am interested in the following decision problem: the input is some elements of $G$ with a partial order on them, and the question is whether there is a permutation of the elements that satisfies the order and is such that the composition of the elements in that order yields the group's neutral element $e$.

Formally, the $G$-test problem is as follows, where the group $G$ is fixed:

• Input: a finite partially ordered set $(P, <)$ with a labeling function $\mu$ from $P$ to $G$.
• Output: whether there exists a linear extension of $P$ (i.e., a total order $(P, <')$ such that for all $x, y \in P$, $x < y$ implies $x <' y$), such that, writing the elements of $P$ following the total order $<'$ as $x_1, \ldots, x_n$, we have $\mu(x_1) \cdot \cdots \cdot \mu(x_n) = e$.

For any group $G$, the $G$-test problem is clearly in NP. My question is: Is there a group $G$ such that the $G$-test problem is NP-hard?

A few remarks about equivalent problem statements:

• The language of posets and linear extensions can be equivalently replaced by that of DAGs and topological orders. That is, if you prefer, you can think of the input as a DAG with vertices labeled with group elements, and as the output as asking whether some topological sort of the input DAG achieves $e$.
• One could instead consider a harder problem where we are given a poset $(P, <)$ and $g \in G$, and ask whether $g$ (rather than $e$) can be realized. In fact the stronger problem reduces to the above: we can ask whether $e$ can be realized by $(P', <)$, where $P'$ is $P$ but with an element labeled $g^{-1}$ which is smaller than all others. Hence the natural choice of $e$ in the above definition.

Now, about my attempts to solve the problem:

• Of course, if the group $G$ is commutative, the $G$-test problem is clearly in PTIME as all linear extensions achieve the same group element, so we can just choose any one of them by topological sort and check whether it is $e$ or not. So the interesting case is non-commutative $G$. More generally, if $G$ has a homomorphism to some non-trivial commutative group (e.g., the signature, for permutations), a necessary but non-sufficient condition is to look at the problem through the homomorphism and check it in PTIME in the commutative image. I fail to see whether this can generalize to a decomposition scheme for all finite groups.
• If the order relation is empty (i.e., we are given a multiset of elements in $G$ and can use any permutation), the problem can be solved by dynamic programming, where the states are the number of occurrences of each element in $G$ that are still not used (remember that $G$ is fixed, so the number of states is then polynomial in the input).
• For inputs that are posets of constant width, we can use a dynamic algorithm following a chain decomposition. So if hardness holds it must be using inputs posets that are arbitrarily wide. Note that for wide posets the number of possible "states" in a dynamic programming approach would be the number of upsets of the poset, which in general is exponential and not polynomial, so that approach does not directly work.
• The same problem could be studied for monoids rather than groups, but for monoids I already know that it is hard, by a fairly convoluted argument that involves the transition monoid of an automaton and reduces to a variant of a previous CStheory question. The full proof of this is in this preprint, appendices D.1.3 and D.1.4, though the terminology is very different. Hence, when $G$-testing is PTIME, it has to use the invertibility of group elements.
• If we asked whether all linear extensions realize $e$ (rather than whether some does), then I know the problem to be in PTIME (see appendix D.2 of the same preprint), though I also know that this other problem would be coNP-hard for monoids rather than groups (D.1.3 and D.1.4).

If $G$-test is hard for some $G$, of course, the natural question is whether some dichotomy holds, and which criterion would distinguish tractable $G$ and non-tractable $G$. In fact this question can be more generally asked when we use finite automata instead of groups. (Formally: Fix a finite alphabet $\Sigma$, and a finite deterministic finite automaton (DFA) $A$ on $\Sigma$, and consider the $A$-test problem, given a poset labeled with elements from $\Sigma$, of checking whether some linear extension forms a word accepted by $A$.) Of course I have no idea about these harder questions.

Answer 1

I show below that the $G$-test problem is NP-hard for some simple but infinite group $G$. The finite case is still open.

proof

Define the following functions: $f(x) = -x$ and $g_a(x) = x + a$.

Then take $G$ to be the group generated by $f$ and $g_a$ with composition as the operation.

Note that the elements of $G$ are $\{f \circ g_a | a \in \mathbb{Z} \} \cup \{g_a | a \in \mathbb{Z} \}$, so this is actually a pretty simple group.

Then the $G$-test problem is NP-hard by reduction from partition.

The partition problem asks for a given sequence of integers $a_1, a_2, ..., a_n$ whether there exists a partition of that sequence into two parts of equal sum.

For any such sequence, we take our poset $P$ to consist of $n+2$ elements with no order imposed. Two of these elements are $f$. The other $n$ elements are $g_{a_i}$ for $i = 1,..., n$.

Note that $g_p \circ g_q = g_{p+q}$ and that $f \circ g_p \circ f = g_{-p}$. Using only these facts, we see that the composition of elements in $P$ in any order will always equal $g_{\sum_{i \not\in I}a_i - \sum_{i \in I}a_i}$ where $I$ is the set of indices for which $g_{a_i}$ was positioned between the two occurrences of $f$. Since the identity is $g_0$, an ordering of $P$ composes into the identity if and only if under that ordering $\sum_{i \not\in I}a_i - \sum_{i \in I}a_i = 0$, or in other words if and only if $\sum_{i \not\in I}a_i = \sum_{i \in I}a_i$.

Then this instance of the $G$-problem has a solution if and only if there exists an $I$ such that $\sum_{i \not\in I}a_i = \sum_{i \in I}a_i$; this is exactly the condition under which the partition instance has a solution.

Thus this reduction is answer preserving. Since it is also clearly polynomial time (assuming any reasonable encoding of elements of $G$), the $G$-test problem is NP-complete.

Answer 2

With my coauthor, we have just posted a preprint which studies this problem more generally for regular languages. In the case of finite groups, we claim that the problem is tractable (in NL) in the case where the partial order on the elements consists of a union of chains: see Theorem 6.2. We would conjecture that the problem for general DAGs is also in NL, and there is some hope of extending the technique to that setting, but we are missing an ingredient for this, related to this question -- for details, see the preprint, Section 6, "Limitations" paragraph at the end, second limitation.