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

<h2>proof</h2>

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

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

<p>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.</p>

<p>Then the $G$-test problem is NP-hard by reduction from partition.</p>

<p>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.</p>

<p>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$.</p>

<p>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$. </p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-08-24T16:45:56.263Z
Thanks a lot. In fact I knew about a reduction from partition to show hardness of $G$-test for an infinite group but using additional expressive power (apx D.1.2 of our preprint), and we hadn't seen how to get hardness of $G$-test from it. It's very interesting that you could do it while still not using the power of imposing an order on elements. Thanks again for pointing this out! As for the finite case, however, we agree that trying to tweak your proof to use bounded sums or modulos and get a finite group would not result in a hard problem, right?
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2015-08-24T15:54:59.070Z
2015-08-24T15:54:59.070Z
Mikhail Rudoy
<p>With my coauthor, we have just posted a <a href="https://arxiv.org/abs/1707.04310" rel="nofollow noreferrer">preprint</a> 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 <a href="https://cstheory.stackexchange.com/questions/37062/generalization-of-dilworths-theorem-for-labeled-dags">this question</a> -- for details, see the preprint, Section 6, "Limitations" paragraph at the end, second limitation.</p>

CC BY-SA 4.0
2017-07-17T06:51:32.237Z
2018-05-11T12:32:28.560Z
2018-05-11T12:32:28.560Z
Antoine Amarilli 'a3nm'
<p>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$.</p>

<p>Formally, the <em>$G$-test problem</em> is as follows, where the group $G$ is fixed:</p>

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

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

<p>A few remarks about equivalent problem statements:</p>

<ul>
<li>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$.</li>
<li>One could instead consider a harder problem where we are given a poset $(P, &lt;)$ 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', &lt;)$, 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.</li>
</ul>

<p>Now, about my attempts to solve the problem:</p>

<ul>
<li>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 <a href="https://en.wikipedia.org/wiki/Parity_of_a_permutation">signature</a>, 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.</li>
<li>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).</li>
<li>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 <a href="https://en.wikipedia.org/wiki/Upper_set">upsets</a> of the poset, which in general is exponential and not polynomial, so that approach does not directly work.</li>
<li>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 <a href="https://cstheory.stackexchange.com/questions/19393/monotone-bijections-between-lists-of-intervals">previous CStheory question</a>. The full proof of this is in <a href="http://pierre.senellart.com/publications/amarilli2016representing.pdf">this preprint</a>, 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. </li>
<li>If we asked whether <em>all</em> linear extensions realize $e$ (rather than whether <em>some</em> 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).</li>
</ul>

<p>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.</p>

CC BY-SA 3.0
2015-08-24T05:06:57.600Z
Are you only interested in results about the $G$-test problem where $G$ is a finite group, or would you be interested an infinite $G$ for which $G$-test is NP-complete?
Mikhail Rudoy
CC BY-SA 3.0
2015-08-24T07:47:49.647Z
For infinite $G$, you probably need to impose complexity bounds on group operations to get anything interesting (what if the composition function is already NP-hard to compute in the input elements?). However, I have no examples of "reasonable" infinite $G$ where hardness holds, so I would also be interested by an example of this.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2015-08-31T04:29:40.667Z
Is there some way to use Barrington's theorem (or something akin to it) here?  I can't figure out how, as I can't figure out how to arrange for long-term correlations between the choices made when selecting the total order, but maybe someone else will see how to do it.
D.W.
<np-hardness><sorting><gr.group-theory><partial-order><order-theory>
Determining what can be achieved by a permutation of elements of a noncommutative group
Antoine Amarilli 'a3nm'
# Determining what can be achieved by a permutation of elements of a noncommutative group

(Asked by: username_0 on 2015-08-23)

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](https://en.wikipedia.org/wiki/Parity_of_a_permutation), 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](https://en.wikipedia.org/wiki/Upper_set) 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](https://cstheory.stackexchange.com/questions/19393/monotone-bijections-between-lists-of-intervals). The full proof of this is in [this preprint](http://pierre.senellart.com/publications/amarilli2016representing.pdf), 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.

**Tags:** np-hardness, sorting, gr.group-theory, partial-order, order-theory
> **Comments:**
> **username_1**: Are you only interested in results about the $G$-test problem where $G$ is a finite group, or would you be interested an infinite $G$ for which $G$-test is NP-complete?  
> **username_0**: For infinite $G$, you probably need to impose complexity bounds on group operations to get anything interesting (what if the composition function is already NP-hard to compute in the input elements?). However, I have no examples of "reasonable" infinite $G$ where hardness holds, so I would also be interested by an example of this.  
> **username_2**: Is there some way to use Barrington's theorem (or something akin to it) here?  I can't figure out how, as I can't figure out how to arrange for long-term correlations between the choices made when selecting the total order, but maybe someone else will see how to do it.  

---

## 2 answers

### Answer by username_1 on 2015-08-24. Score: 2

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.

> **Comments:**
> **username_0**: Thanks a lot. In fact I knew about a reduction from partition to show hardness of $G$-test for an infinite group but using additional expressive power (apx D.1.2 of our preprint), and we hadn't seen how to get hardness of $G$-test from it. It's very interesting that you could do it while still not using the power of imposing an order on elements. Thanks again for pointing this out! As for the finite case, however, we agree that trying to tweak your proof to use bounded sums or modulos and get a finite group would not result in a hard problem, right?  

---

### Answer by username_0 on 2017-07-17. Score: 2

With my coauthor, we have just posted a [preprint](https://arxiv.org/abs/1707.04310) 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](https://cstheory.stackexchange.com/questions/37062/generalization-of-dilworths-theorem-for-labeled-dags) -- for details, see the preprint, Section 6, "Limitations" paragraph at the end, second limitation.


---

