11institutetext:  University of Siegen, Germany 11email:
<EMAIL_ADDRESS>
# Parameterized complexity of factorization problems

Markus Lohrey 11 Andreas Rosowski 11

###### Abstract

We study the parameterized complexity of the following factorization problem:
given elements $a,a_{1},\ldots,a_{m}$ of a monoid and a parameter $k$, can $a$
be written as the product of at most (or exactly) $k$ elements from
$a_{1},\ldots,a_{m}$. Several new upper bounds and fpt-equivalences with more
restricted problems (subset sum and knapsack) are shown. Finally, some new
upper bounds for variants of the parameterized change-making problems are
shown.

##  1 Introduction

This paper deals with the parameterized complexity of factorization problems
in monoids. In the most generic setting, we have a fixed class $\mathsf{C}$ of
monoids. The input consists of a monoid $M\in\mathsf{C}$, elements
$a,a_{1},\dots,a_{m}\in M$ and a positive integer $k$. The question is whether
$a$ can be written as a product of at most $k$ elements from the list
$a_{1},\dots,a_{m}$ (every $a_{i}$ may occur several times in this product).
In the parameterized setting, $k$ is the parameter. This problem has been
studied most intensively for the case, where $\mathsf{C}$ consists of the
class of all symmetric groups $S_{n}$ ($S_{n}$ is the group of all
permutations on the set $\\{1,2,\ldots,n\\}$). The non-parameterized variant
of this problem has been introduced by Even and Goldreich under the name MGS
(for minimum generator sequence) [5], where the problem was shown to be ${\sf
NP}$-complete if $k$ is given in unary notation. This result even holds for
the case, when $\mathsf{C}$ is the class of abelian groups
$\mathbb{Z}_{2}^{n}$ for $n\geq 1$. For the case, where the factorization
length $k$ is given in binary notation, Jerrum [12] proved that MGS is PSPACE-
complete.

Let us now come to the parameterized factorization problem for permutations,
where the parameter is the factorization length $k$. We denote this problem by
$\mathsf{pF}[\mathsf{S}_{*}]$ (the $*$ indicates that the degree $n$ of the
symmetric group $S_{n}$ is part of the input). It was shown by [3, Chapter 11]
that $\mathsf{pF}[\mathsf{S}_{*}]$ is $\mathsf{W}[1]$-hard and hence unlikely
to be fixed parameter tractable. On the other hand, no good upper bound is
known. Interestingly, the parameterized factorization problem for
transformation monoids $T_{n}$ ($T_{n}$ is the monoid consisting of all
mappings on the finite set $\\{1,2,\ldots,n\\}$), which is denoted by
$\mathsf{pF}[\mathsf{T}_{*}]$, is $\mathsf{W}[2]$-hard [2]. It was shown in
[6] that $\mathsf{pF}[\mathsf{T}_{*}]$ is equivalent under fixed parameter
reductions to the problem whether a given deterministic automaton has a
synchronizing word of length at most $k$, where $k$ is the parameter. The
latter problem belongs to the intersection of the parameterized classes
$\mathsf{A}[2]$, $\mathsf{W}[\mathsf{P}]$, and WNL. In particular,
$\mathsf{pF}[\mathsf{T}_{*}]$ also belongs to the classes $\mathsf{A}[2]$,
$\mathsf{W}[\mathsf{P}]$, and WNL. Our first result improves on the membership
in $\mathsf{A}[2]$ by showing that $\mathsf{pF}[\mathsf{T}_{*}]$ belongs to
the class $\mathsf{W}^{\textsf{func}}[2]\subseteq\mathsf{A}[2]$. The classes
$\mathsf{W}^{\textsf{func}}[2]$ and $\mathsf{W}[2]$ are both defined by
parameterized model-checking problems for certain fragments of first-order
logic (see Section 3 for details); the only difference is that $\mathsf{W}[2]$
restricts to formulas without function symbols, whereas
$\mathsf{W}^{\textsf{func}}[2]$ allows also function symbols.

We then proceed with showing that $\mathsf{pF}[\mathsf{S}_{*}]$ is equivalent
with respect to fixed parameter reductions to two apparently simpler problems:
the parameterized knapsack problem for symmetric groups
$\mathsf{pKS}[\mathsf{S}_{*}]$ and the parameterized subset sum problem for
symmetric groups $\mathsf{pSSS}[\mathsf{S}_{*}]$. The problem
$\mathsf{pKS}[\mathsf{S}_{*}]$ is a restricted version of
$\mathsf{pF}[\mathsf{S}_{*}]$ in the sense that only factorizations of the
form $a=a_{1}^{x_{1}}a_{1}^{x_{2}}\cdots a_{m}^{x_{m}}$ with
$x_{1},\ldots,x_{m}\in\mathbb{N}$ and $\sum_{i=1}^{m}x_{i}\leq k$ are allowed.
For $\mathsf{pSSS}[\mathsf{S}_{*}]$ one additionally requires
$x_{1},\ldots,x_{m}\in\\{0,1\\}$. In the classical (unparameterized) setting,
these problems are again NP-complete [14]. When restricting the problems
$\mathsf{pKS}[\mathsf{S}_{*}]$ and $\mathsf{pSSS}[\mathsf{S}_{*}]$ to cyclic
(resp., abelian) permutation groups we show that the resulting problems are
still $\mathsf{W}[1]$-hard and obtain the new upper bounds $\mathsf{W}[3]$ for
the cyclic case and $\mathsf{W}[5]$ for the abelian case.

In the last section of the paper, we deal with the change-making problems
introduced in [10], which are variants of the classical knapsack and subset
sum problems for integers, precise definitions can be found in Section 5. It
was shown in [10] that these change-making problems are $\mathsf{W}[1]$-hard
and contained in $\mathsf{XP}$. We observe that one can improve the upper
bound to $\mathsf{W}[3]$ by using a corresponding upper bound for the
classical subset sum problem from [1]. More interestingly, we also consider
the approximative change making problems from [10] that involve an objective
function $f(x,y)=ax+by$ that has to be minimized. The approximative change
making problems are in $\mathsf{W}[3]$ if $b>0$ or $a=0$ and paraNP-complete
if $b=0$ and $a>0$.

##  2 General notations

We write $\operatorname{poly}(n)$ for an arbitrary polynomial in $n$. The
composition $fg$ of two functions $f,g:A\to A$ is evaluated from the left to
right, i.e., $(fg)(a)=g(f(a))$. Therefore we also write $af$ for $f(a)$. Then
we have $a(fg)=afg$. In order to distinguish better between the argument $a$
and the function $f$ we sometimes also write $a\cdot f$ for $af$.

For a positive integer $N\in\mathbb{N}$ we denote by $\\#(N)$ the number of
bits of $N$. For integers $i\leq j$ we write $[i,j]$ for the interval
$\\{i,i+1,\ldots,j\\}$. Let $T_{n}$ be the set of all mappings on $[1,n]$ and
$S_{n}$ be the set of all permutations on $[1,n]$. With respect to composition
of functions, $T_{n}$ is a monoid (the transformation monoid on $n$ elements)
and $S_{n}$ is a group (the symmetric group on $n$ elements). A permutation
group is a subgroup of $S_{n}$ for some $n$.111By Cayley’s theorem, every
finite group is isomorphic to some subgroup of $S_{n}$. When we talk about a
permutation group $G$, we mean the abstract group $G$ together with its action
on the elements of $[1,n]$. Permutations will be often written by their
decomposition into disjoint cycles, called the disjoint cycle decomposition;
see e.g., [16] for details. A cycle of length two is a transposition.

For a monoid $M$, $A\subseteq M$ and $k\geq 0$ we write $A^{\leq k}$ (resp.,
$A^{k}$) for the set of all products $a_{1}a_{2}\cdots a_{l}\in M$ with $l\leq
k$ (resp., $l=k$) and $a_{1},\ldots,a_{l}\in A$. For a group $G$ and $g\in G$,
its order $\operatorname{ord}(g)$ is the smallest $k\geq 1$ such that
$g^{k}=1$ (let $\operatorname{ord}(g)=\infty$ if such a $k$ does not exist).
For a subset $A\subseteq G$ we denote with $\langle A\rangle$ the subgroup of
$G$ generated by the elements from $A$ (i.e., the closure of $A$ under the
group multiplication). If $\langle A\rangle=G$ then $A$ is a generating set of
$G$.

##  3 Parameterized complexity theory

A parameterized problem is a subset $L\subseteq\Sigma^{*}\times\mathbb{N}$ for
a finite alphabet $\Sigma$. For a pair $(u,k)\in\Sigma^{*}\times\mathbb{N}$ we
call $k$ the parameter. For a fixed number $d\in\mathbb{N}$, the $d^{th}$
slice of $L$ is $L_{d}=\\{(u,d)\in L:u\in\Sigma^{*}\\}$. The class FPT of
fixed parameter tractable problems is the class of all parameterized problems
$L\subseteq\Sigma^{*}\times\mathbb{N}$ for which there is an algorithm
deciding $L$ and running on input $(u,k)$ in time $poly(|u|)\cdot f(k)$ for an
arbitrary computable function $f$. The class paraNP is the class of
parameterized problems that can be solved by a nondeterministic algorithm in
time $poly(|u|)\cdot f(k)$ for an arbitrary computable function $f$.

An fpt-reduction from a parameterized problem
$L_{1}\subseteq\Sigma_{1}^{*}\times\mathbb{N}$ to a parameterized problem
$L_{2}\subseteq\Sigma_{2}^{*}\times\mathbb{N}$ is a computable function
$r:\Sigma_{1}^{*}\times\mathbb{N}\to\Sigma_{2}^{*}\times\mathbb{N}$ such that
the following hold for all $u\in\Sigma_{1}^{*}$ and $k\in\mathbb{N}$:

  * •

there are functions $g,h$ such that $r(u,k)=(g(u,k),h(k))$,

  * •

$r(u,k)$ can be computed in time $poly(|u|)f(k)$ for a computable function
$f$,

  * •

$(u,k)\in L_{1}$ if and only if $r(u,k)\in L_{2}$.

We write $L_{1}\leq^{\mathsf{fpt}}L_{2}$ if there is an fpt-reduction from
$L_{1}$ to $L_{2}$. We write $L_{1}\equiv^{\mathsf{fpt}}L_{2}$ for
$L_{1}\leq^{\mathsf{fpt}}L_{2}\leq^{\mathsf{fpt}}L_{1}$ ($L_{1}$ and $L_{2}$
are equivalent with respect to fpt-reductions). Moreover, for the
parameterized problem $L$ we define the class $[L]^{\mathsf{fpt}}$ as the
class of all parameterized problems $K$ with $K\leq^{\mathsf{fpt}}L$. Note
that it makes no difference in the above definitions, whether the parameter
$k$ is given in binary or unary representation, since it enters the running
time with an arbitrary computable function $f(k)$.

Of particular importance in parameterized complexity theory are model-checking
problems for fragments of first-order logic. Let $\mathsf{C}$ be a set of
closed first-order formulas. Then the problem $\mathsf{pMC}(\mathsf{C})$ is
defined as follows:

######  Problem 1 (parameterized model-checking problem for $C$,
$\mathsf{pMC}(\mathsf{C})$ for short)

Input: a formula $F\in\mathsf{C}$ and a structure $\mathcal{A}$
Parameter: the length $|F|$ of the formula $F$
Question: Does $\mathcal{A}\models F$ hold?

We now define several well-known parameterized complexity classes by taking
for $\mathsf{C}$ certain fragments of first-order logic. For $l\geq 1$ we
define $\Sigma_{l}$ as the class of first-order formulas of the form
$\exists\overline{x}_{1}\forall\overline{x}_{2}\cdots
Q_{l}\overline{x}_{l}\psi$, where $\psi$ is a relational quantifier-free
formula (i.e., no function symbols appear in $\psi$), $Q_{l}=\exists$ if $l$
is odd, $Q_{l}=\forall$ if $l$ is even, and every $\overline{x}_{i}$ is a
tuple of variables of arbitrary length. If we require in addition that every
tuple $\overline{x}_{i}$ with $2\leq i\leq l$ has at most $u$ variables, we
obtain the class of formulas $\Sigma_{l,u}$. For $l\geq 1$ and $m\geq 0$ we
define $\Sigma^{l,m}$ as the class of $\Sigma_{l+m}$-formulas
$\exists\overline{x}_{1}\forall\overline{x}_{2}\cdots
Q_{l}\overline{x}_{l}Q_{l+1}x_{l+1}\cdots Q_{l+m}x_{l+m}\psi$, where
$x_{l+1},\ldots,x_{l+m}$ are single variables.

If we allow also function symbols and constants in the above formula classes,
we obtain the formula classes $\Sigma^{\mathsf{func}}_{l}$ and
$\Sigma^{\mathsf{func}}_{l,u}$ and $\Sigma^{l,m,\mathsf{func}}$.

We then define the following parameterized complexity classes, where $l,t\geq
1$:

$\displaystyle\textsf{W}[l]$ $\displaystyle\ =\
\big{[}\mathsf{pMC}\big{(}\bigcup_{u\geq
1}\Sigma_{l,u}\big{)}\big{]}^{\textsf{fpt}}=[\mathsf{pMC}(\Sigma_{l,1})]^{\textsf{fpt}}$
[8, Theorem 7.22] (1) $\displaystyle\textsf{A}[l]$ $\displaystyle\ =\
[\mathsf{pMC}(\Sigma_{l})]^{\textsf{fpt}}$ [8, Definition 5.7]
$\displaystyle\textsf{A}[l,t]$ $\displaystyle\ =\
[\textsf{pMC}(\Sigma^{l,t-1})]^{\textsf{fpt}}$ [8, Theorem 8.44]
$\displaystyle\textsf{W}^{\textsf{func}}[l]$ $\displaystyle\ =\
\big{[}\mathsf{pMC}\big{(}\bigcup_{u\geq
1}\Sigma_{l,u}^{\mathsf{func}}\big{)}\big{]}^{\textsf{fpt}}$ [8, Definition
8.56] $\displaystyle\textsf{A}^{\textsf{func}}[l]$ $\displaystyle\ =\
[\mathsf{pMC}(\Sigma^{\mathsf{func}}_{l})]^{\textsf{fpt}}$
$\displaystyle\textsf{A}^{\textsf{func}}[l,t]$ $\displaystyle\ =\
[\textsf{pMC}(\Sigma^{l,t-1,\textsf{func}})]^{\textsf{fpt}}$

We clearly have $\textsf{W}[l]\subseteq\textsf{W}^{\textsf{func}}[l]$ and
analogously for $\textsf{A}[l]$ and $\textsf{A}[l,t]$. Here are a few other
relationships (that hold for all $l\geq 1$) between these classes; see [8]:

$\displaystyle\mathsf{A}[l,1]\ =\ \mathsf{A}[l]$ $\displaystyle=$
$\displaystyle\mathsf{A}^{\mathsf{func}}[l]\ =\
\textsf{A}^{\mathsf{func}}[l,1]$ (2)
$\displaystyle\mathsf{W}[t]=\textsf{A}[1,t]\quad$ and
$\displaystyle\quad\mathsf{W}^{\mathsf{func}}[t]=\mathsf{A}^{\mathsf{func}}[1,t]$
$\displaystyle\mathsf{A}[l,t]\subseteq\mathsf{A}[l+1,t-1]\quad$ and
$\displaystyle\quad\mathsf{A}^{\mathsf{func}}[l,t]\subseteq\mathsf{A}^{\mathsf{func}}[l+1,t-1]$

Here, the equality $\mathsf{A}[l]=\mathsf{A}^{\mathsf{func}}[l]$ in (2)
follows from
$\mathsf{pMC}(\Sigma^{\mathsf{func}}_{l})\leq_{\mathsf{fpt}}\mathsf{pMC}(\Sigma_{l})$;
see [8, p. 201]. The equality $\textsf{W}[t]=\textsf{A}[1,t]$ is a direct
consequence of the second equality in (1), whereas a proof of
$\mathsf{W}^{\mathsf{func}}[t]=\mathsf{A}^{\mathsf{func}}[1,t]$ can be found
in Appendix 0.A. A consequence of the above relationships is
$\mathsf{A}[2,2]\subseteq\mathsf{A}^{\mathsf{func}}[2,2]\subseteq\mathsf{A}[3]$.

##  4 Parameterized complexity of factorization problems

###  4.1 Generic variants of factorization problems

Let $\mathsf{C}$ be a class of monoids. Every monoid $M\in\mathsf{C}$ must
have a finite representation that we define later for the classes considered
in this paper. Also elements of $M$ must have a finite representation. The
parameterized factorization problem for the class $\mathsf{C}$ is the
following problem:

######  Problem 2 (parameterized factorization problem for the class
$\mathsf{C}$, $\mathsf{pF}[\mathsf{C}]$ for short)

Input: a monoid $M\in\mathsf{C}$, elements $a,a_{1},\dots,a_{m}\in M$ and
$k\in\mathbb{N}$ (the parameter)
Question: Does $a\in\\{a_{1},\dots,a_{m}\\}^{k}$ hold?

We also consider two variants of $\mathsf{pF}[\mathsf{C}]$ by restricting the
order in which the elements $a_{1},\dots,a_{m}$ may occur in a factorization
of $a$.

######  Problem 3 (parameterized knapsack for $\mathsf{C}$,
$\mathsf{pKS}[\mathsf{C}]$ for short)

Input: a monoid $M\in\mathsf{C}$, elements $a,a_{1},\dots,a_{m}\in M$ and
$k\in\mathbb{N}$ (the parameter)
Question: Are there $x_{1},\dots,x_{m}\in\mathbb{N}$ with
$\sum_{i=1}^{m}x_{i}=k$ and $a=a_{1}^{x_{1}}\cdots a_{m}^{x_{m}}$?

######  Problem 4 (parameterized subset sum for $\mathsf{C}$,
$\mathsf{pSSS}[\mathsf{C}]$ for short)

Input: a monoid $M\in\mathsf{C}$, elements $a,a_{1},\dots,a_{m}\in M$ and
$k\in\mathbb{N}$ (the parameter)
Question: Are there $x_{1},\dots,x_{m}\in\\{0,1\\}$ with
$\sum_{i=1}^{m}x_{i}=k$ and $a=a_{1}^{x_{1}}\cdots a_{m}^{x_{m}}$?

Note that when $\mathsf{C}$ only contains commutative monoids, there is no
difference between $\mathsf{pF}[\mathsf{C}]$ and $\mathsf{pKS}[\mathsf{C}]$.
In this case, we only consider the problems $\mathsf{pKS}[\mathsf{C}]$ and
$\mathsf{pSSS}[\mathsf{C}]$. If $\mathsf{C}=\\{M\\}$ consists of only one
monoid, we write $\mathsf{pSSS}[M]$ instead of $\mathsf{pSSS}[\\{M\\}]$ and
analogously for the other problems.

###### Definition 1

We consider the following cases for the class $\mathsf{C}$:

  * •

$\mathsf{T}_{*}:=\\{T_{n}:n\geq 1\\}$ is the class of all transformation
monoids. The transformation monoid $T_{n}$ is simply represented by the number
$n$ in unary representation and a function $f\in T_{n}$ is represented by the
list $[f(1),f(2),\ldots,f(n)]$. The problem $\mathsf{pF}[\mathsf{T}_{*}]$ has
been considered in [2].

  * •

$\mathsf{S}_{*}:=\\{S_{n}:n\geq 1\\}$ is the class of all symmetric groups. We
inherit the above input representation for $\mathsf{T}_{*}$.

  * •

$\mathsf{AbPG}$ is the class of abelian permutation groups. An abelian
permutation group is represented by a list of pairwise commuting generators
$\pi_{1},\ldots,\pi_{m}\in S_{n}$ (for some $n$). Elements of
$\langle\pi_{1},\ldots,\pi_{m}\rangle$ are simply represented by permutations
(by [9] one can check in polynomial time, whether a given permutation belongs
to $\langle\pi_{1},\ldots,\pi_{m}\rangle$).

  * •

$\mathsf{CycPG}$ is the class of cyclic permutation groups. We use the same
input representation as for $\mathsf{AbPG}$. In Appendix 0.G we will show that
given a list of permutations $\pi_{1},\ldots,\pi_{m}$ one can check in
polynomial time, whether the permutation group
$\langle\pi_{1},\ldots,\pi_{m}\rangle$ is cyclic. In the positive case one can
compute in polynomial time a permutation $\pi$ with
$\langle\pi\rangle=\langle\pi_{1},\ldots,\pi_{m}\rangle$.

  * •

the singleton classes $\\{\mathbb{Z}\\}$ and $\\{\mathbb{N}\\}$ with addition
as the monoid operation: in these cases, there is of course no reason to
choose an input representation for the monoid. Elements of $\mathbb{Z}$ or
$\mathbb{N}$ are represented in binary representation.

  * •

$\mathbb{Z}^{*}:=\\{\mathbb{Z}^{n}:n\geq 1\\}$ and
$\mathbb{N}^{*}:=\\{\mathbb{N}^{n}:n\geq 1\\}$, where $\mathbb{Z}^{n}$ (resp.,
$\mathbb{N}^{n}$) is represented by the unary encoding of $n$ and groups
elements are represented by $n$-tuples of binary encodings. The operation is
vector addition.

  * •

$\mathsf{FAbG}$ is the class of finite abelian groups, where the finite
abelian group $G=\prod_{i=1}^{d}\mathbb{Z}_{n_{i}}$ is represented by the
tuple $(n_{1},n_{2},\ldots,n_{d})$ with each $n_{i}$ given in binary
representation. An element of $G$ is given by a tuple
$(a_{1},a_{2},\ldots,a_{d})$ with each $a_{i}\in[0,n_{i}-1]$ given in binary
representation.

  * •

$\mathsf{FCycG}:=\\{\mathbb{Z}_{n}:n\geq 2\\}$ is the class of finite cyclic
groups (with $n$ again given in binary notation).

The classes except for $\mathsf{C}=\mathsf{T}_{*}$ and
$\mathsf{C}=\mathsf{S}_{*}$ are called the commutative classes in the rest of
the paper. For those classes we do not consider $\mathsf{pF}[\mathsf{C}]$
since it is equivalent to $\mathsf{pKS}[\mathsf{C}]$.

###### Remark 1

Note that as abstract classes of groups, $\mathsf{CycPG}$ and $\mathsf{FCycG}$
(resp., $\mathsf{AbPG}$ and $\mathsf{FAbG}$) are the same, but there is a
difference in the succinctness of descriptions. In general, if
$\gamma_{1},\ldots,\gamma_{d}$ are the pairwise disjoint cycles of a
permutation $\pi\in S_{n}$, and $\ell_{i}\in[1,n]$ is the length of
$\gamma_{i}$, then
$\operatorname{ord}(\pi)=\operatorname{lcm}(\ell_{1},\ldots,\ell_{d})$. In
particular, every prime power $p^{e}$ that divides $\operatorname{ord}(\pi)$
is bounded by $n$. Therefore the cyclic permutation group
$\langle\pi\rangle\leq S_{n}$ is isomorphic to $\mathbb{Z}_{m}$, where all
prime powers in $m$ are bounded by $n$ (recall that $n$ is given in unary
representation in our setting). Hence, if for instance,
$\mathbb{Z}_{2^{m}}\cong\langle\pi\rangle$ for $\pi\in S_{n}$, then $n\geq
2^{m}$ and the encoding of $\pi$ (a list of $n$ numbers from $[1,n]$) needs at
least $2^{m}\cdot m$ bits.

###### Remark 2

For an abelian permutation group $\langle\pi_{1},\ldots,\pi_{m}\rangle$ we
represent an element $\pi\in\langle\pi_{1},\ldots,\pi_{m}\rangle$ as a
permutation. Alternatively, we could represent $\pi$ by binary encoded
exponents $k_{1},\ldots,k_{m}\in\mathbb{N}$ such that
$\pi=\pi_{1}^{k_{1}}\cdots\pi_{m}^{k_{m}}$. These two representations are
equivalent in the sense that one can change in polynomial time between the two
representations. One direction is clear: given binary encoded numbers
$k_{1},\ldots,k_{m}$ one can compute by iterated squaring the permutation
$\pi_{1}^{k_{1}}\cdots\pi_{m}^{k_{m}}$. On the other hand, given a permutation
$\pi\in\langle\pi_{1},\ldots,\pi_{m}\rangle$, the algorithm from [9] allows to
compute in polynomial time a straight-line program over
$\pi_{1},\ldots,\pi_{m}$ for $\pi$. This is a context-free grammar that
produces a single word $w$ over the letters $\pi_{1},\ldots,\pi_{m}$ that
evaluates to $\pi$. One can then easily compute in polynomial time the number
of occurrences of every $\pi_{i}$ in $w$.

In some papers, one finds the alternative of $\mathsf{pF}[\mathsf{C}]$, where
the condition $a\in\\{a_{1},\dots,a_{m}\\}^{k}$ is replaced by
$a\in\\{a_{1},\dots,a_{m}\\}^{\leq k}$. Similarly, in
$\mathsf{pKS}[\mathsf{C}]$ and $\mathsf{pSSS}[\mathsf{C}]$ one could replace
the condition $\sum_{i=1}^{m}x_{i}=k$ by $\sum_{i=1}^{m}x_{i}\leq k$. Let us
denote these problems with $\mathsf{pF}_{\leq}[\mathsf{C}]$,
$\mathsf{pKS}_{\leq}[\mathsf{C}]$, and $\mathsf{pSSS}_{\leq}[\mathsf{C}]$,
respectively.

For the subset sum problems one also finds the variants, where the $a_{i}$ are
assumed to be pairwise different. These variants will be denoted with
$\mathsf{pSSS}^{\neq}[\mathsf{C}]$ and
$\mathsf{pSSS}_{\leq}^{\neq}[\mathsf{C}]$. In the case where $\mathsf{C}$
consists of commutative monoids, one can define these problems also as
follows: given a monoid $M\in\mathsf{C}$, a finite subset $A\subseteq M$, an
element $a\in M$ and the parameter $k$, the question is whether there is a
subset $S\subseteq A$ with $|S|=k$ (resp., $|S|\leq k$) and $\sum_{b\in
A}b=a$. The problem $\mathsf{pSSS}^{\neq}[\mathbb{Z}]$ was studied in [1],
whereas $\mathsf{pSSS}[\mathbb{Z}]$ is the variant studied in [4]. We will
later show that the above variants of subset sum are all equivalent with
respect to fpt-reductions for the classes $\mathsf{C}$ from Definition 1.

By replicating group elements in the input (see Appendix 0.B) one obtains:

###### Lemma 1

For every class $\mathsf{C}$ we have
$\mathsf{pF}[\mathsf{C}]\leq^{\mathsf{fpt}}\mathsf{pKS}[\mathsf{C}]\leq^{\mathsf{fpt}}\mathsf{pSSS}[\mathsf{C}]$
and
$\mathsf{pF}_{\leq}[\mathsf{C}]\leq^{\mathsf{fpt}}\mathsf{pKS}_{\leq}[\mathsf{C}]\leq^{\mathsf{fpt}}\mathsf{pSSS}_{\leq}[\mathsf{C}]$.

###  4.2 Factorization in transformation monoids

In [2] it was shown that $\mathsf{pF}[\mathsf{T}_{*}]$ is
$\mathsf{W}[2]$-hard. The complexity of $\mathsf{pF}[\mathsf{T}_{*}]$ was
related in [6] to another parameterized problem. For a deterministic finite
automaton $A$ a synchronizing word $w$ for $A$ has the property that there
exists a state $q$ such that for every state $p$, $w$ leads from $p$ to $q$.
The following problem has been introduced in [7]; see also [6].

######  Problem 5 ($\mathsf{p\text{-}DFA\text{-}SW}$ [6])

Input: DFA $A$, $k\in\mathbb{N}$ (the parameter)
Question: Is there a synchronizing word $w$ for $A$ with $|w|\leq k$?

It is known that p-DFA-SW $\equiv^{\mathsf{fpt}}\mathsf{pF}[\mathsf{T}_{*}]$
[6] and that $\mathsf{p\text{-}DFA\text{-}SW}$ belongs to the intersection of
the classes $\mathsf{A}[2]$, $\mathsf{W[P]}$, and $\mathsf{WNL}$ [7]. The
complexity class $\mathsf{W}[\textsc{sync}]$ was defined in [6] as
$\mathsf{W}[\textsc{sync}]=[\mathsf{p\text{-}DFA\text{-}SW}]^{\mathsf{fpt}}$.
Therefore, $\mathsf{pF}[\mathsf{T}_{*}]$ is
$\mathsf{W}[\textsc{sync}]$-complete and belongs to the intersection of the
classes $\mathsf{A}[2]$, $\mathsf{W[P]}$, and $\mathsf{WNL}$. Note that
$\mathsf{W}^{\mathsf{func}}[2]\subseteq\mathsf{A}^{\mathsf{func}}[2]=\mathsf{A}[2]$.
Therefore, the following result improves upon the membership of
$\mathsf{pF}[\mathsf{T}_{*}]$ in $\mathsf{A}[2]$.

###### Theorem 4.1

$\mathsf{pF}[\mathsf{T}_{*}]$ belongs to $\mathsf{W}^{\mathsf{func}}[2]$.

The proof can be found in Appendix 0.C and consists of an fpt-reduction from
$\mathsf{pF}[\mathsf{T}_{*}]$ to $\mathsf{pMC}(\Sigma_{2,1}^{\mathsf{func}})$.
Since $\mathsf{pF}[\mathsf{T}_{*}]$ is $\mathsf{W}[\textsc{sync}]$-complete
[6], we obtain:

###### Corollary 1

$\mathsf{W}[\textsc{sync}]\subseteq\mathsf{W}^{\mathsf{func}}[2]$.

###  4.3 Factorization in symmetric groups and transformation groups

We now show that the various variants of factorization problems for symmetric
groups are equivalent with respect to fpt-reductions:

###### Theorem 4.2

Let $\mathsf{C}$ be either the class $\mathsf{T}_{*}$ or $\mathsf{S}_{*}$.
Then the problems $\mathsf{pF}[\mathsf{C}]$, $\mathsf{pF}_{\leq}[\mathsf{C}]$,
$\mathsf{pKS}[\mathsf{C}]$, $\mathsf{pKS}_{\leq}[\mathsf{C}]$,
$\mathsf{pSSS}[\mathsf{C}]$, $\mathsf{pSSS}^{\neq}[\mathsf{C}]$,
$\mathsf{pSSS}_{\leq}[\mathsf{C}]$, and
$\mathsf{pSSS}_{\leq}^{\neq}[\mathsf{C}]$ are equivalent with respect to fpt-
reductions.

###### Proof

The fpt-equivalence of $\mathsf{pSSS}[\mathsf{C}]$,
$\mathsf{pSSS}^{\neq}[\mathsf{C}]$, $\mathsf{pSSS}_{\leq}[\mathsf{C}]$, and
$\mathsf{pSSS}_{\leq}^{\neq}[\mathsf{C}]$ is stated in Corollary 2 in Appendix
0.E. Moreover, the fpt-equivalence of $\mathsf{pF}[\mathsf{C}]$ and
$\mathsf{pF}_{\leq}[\mathsf{C}]$ (respectively, $\mathsf{pKS}[\mathsf{C}]$ and
$\mathsf{pKS}_{\leq}[\mathsf{C}]$) follows from Lemmas 4 and 5 in Appendix
0.E. It suffices to show
$\mathsf{pSSS}[\mathsf{T}_{*}]\leq^{\mathsf{fpt}}\mathsf{pF}[\mathsf{T}_{*}]$
and
$\mathsf{pSSS}[\mathsf{S}_{*}]\leq^{\mathsf{fpt}}\mathsf{pF}[\mathsf{S}_{*}]$.
We only prove the statement for $\mathsf{S}_{*}$, the same proof can be also
used for $\mathsf{T}_{*}$.

Let $\pi,\pi_{1},\dots,\pi_{m}\in S_{n}$ and $k\in\mathbb{N}$ be the input
data for $\mathsf{pSSS}[\mathsf{S}_{*}]$. W.l.o.g. we can assume that $k\geq
4$. For $i<j$ we use $\llbracket i,j\rrbracket$ to denote the cycle
$(i,i+1,\dots,j)$. Let $n_{0}=n+k+3$ and $\beta=\llbracket
n+1,n_{0}-1\rrbracket$. For $l\in[1,m+1]$ we define the cycle
$\gamma_{l}=\llbracket n_{0}+(l-1)k,n_{0}+lk\rrbracket$. Note that consecutive
cycles $\gamma_{l}$ and $\gamma_{l+1}$ intersect in the point $n_{0}+lk$.

We define an instance of $\mathsf{pF}[\mathsf{S}_{*}]$. The group generators
are

$\displaystyle\tau_{i,j}$ $\displaystyle\ =\
\pi_{j}\beta\prod_{l=i}^{j}\gamma_{l}$ for $\displaystyle
j\in[1,m],i\in[1,j]\text{ and }$ $\displaystyle\tau_{i,m+1}$ $\displaystyle\
=\ \beta\prod_{l=i}^{m+1}\gamma_{l}$ for $\displaystyle i\in[1,m+1].$

Finally we define the permutation $\tau$ to be factored by

$\tau=\pi\beta^{k+1}\prod_{l=1}^{m+1}\gamma_{l}.$

Note that the cycle $\beta$ has length $k+2$ and is disjoint from the cycles
$\gamma_{l}$ and also disjoint to permutations from $S_{n}$.

We show that there exist $x_{1},\ldots,x_{m}\in\\{0,1\\}$ with
$\sum_{i=1}^{m}x_{i}=k$ and $\pi=\pi_{1}^{x_{1}}\cdots\pi_{m}^{x_{m}}$ iff
$\tau\in\\{\tau_{i,j}\mid 1\leq i\leq j\leq m+1\\}^{\leq k+1}$. First suppose
that there exist $x_{1},\ldots,x_{m}\in\\{0,1\\}$ with $\sum_{i=1}^{m}x_{i}=k$
and $\pi=\pi_{1}^{x_{1}}\cdots\pi_{m}^{x_{m}}$. In other words, we can write
$\pi=\pi_{i_{1}}\cdots\pi_{i_{k}}$ with strictly increasing indices $1\leq
i_{1}<\dots<i_{k}\leq m$. Note that since the indices are strictly increasing
we have $i_{d}\geq i_{d-1}+1$ and $m+1\geq i_{k}+1$. Thus
$\tau_{i_{d-1}+1,i_{d}}$ and $\tau_{i_{k}+1,m+1}$ are defined. We obtain

$\displaystyle\tau_{1,i_{1}}\bigg{(}\prod_{d=2}^{k}\tau_{i_{d-1}+1,i_{d}}\bigg{)}\tau_{i_{k}+1,m+1}$
$\displaystyle=$
$\displaystyle\pi_{i_{1}}\beta\prod_{l=1}^{i_{1}}\gamma_{l}\cdot\prod_{d=2}^{k}\bigg{(}\pi_{i_{d}}\beta\\!\\!\\!\prod_{l=i_{d-1}+1}^{i_{d}}\\!\\!\\!\gamma_{l}\bigg{)}\cdot\beta\\!\\!\\!\prod_{l=i_{k}+1}^{m+1}\\!\\!\gamma_{l}$
$\displaystyle=$
$\displaystyle\pi_{i_{1}}\cdots\pi_{i_{k}}\beta^{k+1}\cdot\prod_{l=1}^{i_{1}}\gamma_{l}\cdot\prod_{d=2}^{k}\prod_{l=i_{d-1}+1}^{i_{d}}\\!\\!\\!\\!\gamma_{l}\cdot\\!\\!\prod_{l=i_{k}+1}^{m+1}\\!\\!\\!\gamma_{l}$
$\displaystyle=$
$\displaystyle\pi_{i_{1}}\cdots\pi_{i_{k}}\beta^{k+1}\prod_{l=1}^{m+1}\gamma_{l}\
=\ \tau.$

By this we obtain $\tau\in\\{\tau_{i,j}\mid 1\leq i\leq j\leq m+1\\}^{\leq
k+1}$.

Now suppose $\tau\in\\{\tau_{i,j}\mid 1\leq i\leq j\leq m+1\\}^{\leq k+1}$.
Then $\tau$ is generated by a sequence of $h\leq k+1$ permutations. Hence
there are numbers $j_{1},\dots,j_{h}\in[1,m+1]$ and for every $d\in[1,h]$
numbers $i_{d}\in[1,j_{d}]$ such that

$\tau=\prod_{d=1}^{h}\tau_{i_{d},j_{d}}.$ (3)

This implies $\beta^{k+1}=\beta^{h}$, which yields $h=k+1$. Moreover (3)
implies

$\prod_{l=1}^{m+1}\gamma_{l}=\prod_{d=1}^{k+1}\prod_{l=i_{d}}^{j_{d}}\gamma_{l}.$
(4)

###### Claim 1

If (4) holds then for all $l\in[1,m+1]$ the cycle $\gamma_{l}$ occurs in the
right-hand side of (4) exactly once.

If a cycle $\gamma_{l}$ does not appear in the right-hand side of (4), then
the point $n_{0}+(l-1)k+1$ is not moved by the right-hand side of (4) but it
is moved by the left-hand side (recall that $k\geq 4$). Hence, every cycle
$\gamma_{l}$ ($l\in[1,m+1]$) must appear in the right-hand side.

Now suppose that a cycle $\gamma_{s}$ for some $s\in[1,m+1]$ occurs more than
once in the right-hand side. We have

$(n_{0}+(s-1)k+1)\cdot{\prod_{l=1}^{m+1}\gamma_{l}}=n_{0}+(s-1)k+2.$

In the following we consider the first two occurences of $\gamma_{s}$ at the
right-hand side and suppose that these occurrences are among the first $e\geq
2$ cycles $\gamma_{l}$ and any further occurrence of $\gamma_{s}$ is beyond
the first $e$ cycles. Then we have

$(n_{0}+(s-1)k+1)\cdot{\prod_{d=1}^{k+1}\prod_{l=i_{d}}^{j_{d}}\gamma_{l}}=(n_{0}+(s-1)k+3)\cdot{\prod_{d=e+1}^{k+1}\prod_{l=i_{d}}^{j_{d}}\gamma_{l}}.$

Here we use the fact that every cycle $\gamma_{l}$ has length $k+1$ and $k\geq
4$. We obtain

$(n_{0}+(s-1)k+3)\cdot{\prod_{d=e+1}^{k+1}\prod_{l=i_{d}}^{j_{d}}\gamma_{l}}=n_{0}+(s-1)k+2.$
(5)

Since for every cycle $\gamma_{r}$ with $r\neq s$ and every $z\in[1,k-1]$ we
have

$(n_{0}+(s-1)k+z)\cdot{\gamma_{r}}=n_{0}+(s-1)k+z,$

equation (5) can only hold if the product
$\prod_{d=e+1}^{k+1}\prod_{l=i_{d}}^{j_{d}}\gamma_{l}$ contains $k$ further
occurrences of $\gamma_{s}$ (we have
$(n_{0}+(s-1)k+3)\cdot{\gamma_{s}^{k}}=(n_{0}+(s-1)k+3)\cdot{\gamma_{s}^{-1}}=n_{0}+(s-1)k+2$).
However, the product $\prod_{d=e+1}^{k+1}\prod_{l=i_{d}}^{j_{d}}\gamma_{l}$
contains at most $k+1-e\leq k-1$ further occurrences of $\gamma_{s}$. By this
it follows

$(n_{0}+(s-1)k+1)\cdot{\prod_{d=1}^{k+1}\prod_{l=i_{d}}^{j_{d}}\gamma_{l}}\neq
n_{0}+(s-1)k+2,$

which is a contradiction. This proves Claim 1 ∎

###### Claim 2

If (4) holds and $r<s$ then $\gamma_{r}$ appears before $\gamma_{s}$ in the
right-hand side of (4).

By Claim 1 we can assume that every cycle $\gamma_{l}$ is contained in the
right-hand side of (4) exactly once. Assume that $r<s$ and $\gamma_{s}$
appears before $\gamma_{r}$. We will deduce a contradiction. We can assume
that the difference $s-r$ is minimal in the sense that there is no $y$ such
that $r<y<s$ and $\gamma_{s}$ appears before $\gamma_{y}$ or $\gamma_{y}$
appears before $\gamma_{r}$. In this case we must have $s=r+1$. Otherwise we
have $s-r\geq 2$. If we then consider the cycle $\gamma_{r+1}$, we obtain a
contradiction to the minimality of $s-r$ in case $\gamma_{s}$ appears before
$\gamma_{r+1}$ (since $s-(r+1)<s-r$) as well as in case $\gamma_{r+1}$ appears
before $\gamma_{s}$ (since then also $\gamma_{r+1}$ appears before
$\gamma_{r}$ and $r+1-r=1<2\leq s-r$).

Let $r_{1},\dots,r_{m+1}\in\\{1,\dots,m+1\\}$ with $r_{i}\neq r_{j}$ for
$i\neq j$ be the sequence of numbers such that

$\prod_{d=1}^{k+1}\prod_{l=i_{d}}^{j_{d}}\gamma_{l}=\prod_{l=1}^{m+1}\gamma_{r_{l}}$

(this should be seen as an identity between words over the letters
$\gamma_{l}$). Thus, we have

$\prod_{l=1}^{m+1}\gamma_{r_{l}}=\prod_{l=1}^{m+1}\gamma_{l}$ (6)

Since $s=r+1$, there are $p<q$ such that $r_{p}=r+1$ and $r_{q}=r$. We obtain

$\displaystyle(n_{0}+rk-1)\cdot{\prod_{l=1}^{m+1}\gamma_{r_{l}}}$
$\displaystyle=$
$\displaystyle(n_{0}+rk-1)\cdot{\prod_{l=q}^{m+1}\gamma_{r_{l}}}$
$\displaystyle=$
$\displaystyle(n_{0}+rk)\cdot{\prod_{l=q+1}^{m+1}\gamma_{r_{l}}}=n_{0}+rk.$

On the other hand, we have

$\displaystyle(n_{0}+rk-1)\cdot{\prod_{l=1}^{m+1}\gamma_{l}}\ =\ $
$\displaystyle(n_{0}+rk-1)\cdot{\prod_{l=r}^{m+1}\gamma_{l}}$ $\displaystyle\
=\ $ $\displaystyle(n_{0}+rk)\cdot{\prod_{l=r+1}^{m+1}\gamma_{l}}$
$\displaystyle=\ $
$\displaystyle(n_{0}+rk+1)\cdot{\prod_{l=r+2}^{m+1}\gamma_{l}}$
$\displaystyle\ =\ $ $\displaystyle n_{0}+rk+1.$

This contradicts (6). ∎

From Claim 1 it follows that in equation (4) the intervals $[i_{d},j_{d}]$ for
$d\in[1,k+1]$ form a partition of $[1,m+1]$. Moreover, by Claim 2 we must have
$j_{d}<i_{d+1}$ for all $d\in[1,k]$. This implies $i_{1}=1$, $i_{d+1}=j_{d}+1$
for all $d\in[1,k]$ and $j_{k+1}=m+1$. Recall that every generator
$\tau_{i,j}$ for $1\leq i\leq j\leq m$ includes the permutation $\pi_{j}\in
S_{n}$. Hence, from (3) we get $\pi=\pi_{j_{1}}\pi_{j_{2}}\cdots\pi_{j_{k}}$
with $j_{1}<j_{2}<\cdots<j_{k}$. ∎

A problem related to the factorization problem in symmetric groups is the
following diameter problem [5, 13]. For a set of permutations $B\subseteq
S_{n}$, its diameter $d(B)$ is the smallest number $d$ such that $\langle
B\rangle=B^{\leq d}$. Note that such a $d$ exists since $S_{n}$ is finite.

######  Problem 6 (p-Diameter)

Input: a unary encoded number $n$, a set of permutations $B\subseteq S_{n}$
and $k\in\mathbb{N}$ (the parameter)
Question: Is $d(B)\leq k$?

With $\mathsf{co\text{-}p\text{-}Diameter}$ we denote the complementary
problem, where it is asked whether $d(B)>k$. The unparameterized version of
$\mathsf{p\text{-}Diameter}$ was recently shown to be
$\Pi_{2}^{\mathsf{P}}$-complete [13]. The proof of the following problem can
be found in Appendix 0.D.

###### Theorem 4.3

There is an fpt-reduction from $\mathsf{co\text{-}p\text{-}Diameter}$ to
$\mathsf{pMC}(\Sigma^{2,1,\mathsf{func}})$. In particular,
$\mathsf{co\text{-}p\text{-}Diameter}$ belongs to
$\mathsf{A}^{\mathsf{func}}[2,2]$.

###  4.4 Factorization in the commutative setting

For the commutative classes from Definition 1 with the exception of
$\mathsf{FAbG}$ and $\mathsf{AbPG}$, we can show the equivalence (with respect
to fpt-reductions) for all our factorization problems; see Appendix 0.F for
the proof.

###### Theorem 4.4

All problems $\mathsf{pX}[\mathsf{C}]$ for
$\mathsf{X}\in\\{\mathsf{KS},\mathsf{KS}_{\leq},\mathsf{SSS},\mathsf{SSS}_{\leq},\mathsf{SSS}^{\neq},\mathsf{SSS}^{\neq}_{\leq}\\}$
and
$\mathsf{C}\in\\{\mathsf{CycPG},\mathsf{FCycG},\mathbb{N},\mathbb{Z},\mathbb{N}^{*},\mathbb{Z}^{*}\\}$
are equivalent with respect to fpt-reductions. Moreover all these problems are
$\mathsf{W}[1]$-hard and contained in $\mathsf{W}[3]$.

The statements concerning $\mathsf{W}[1]$ and $\mathsf{W}[3]$ follow from [4]
(where $\mathsf{W}[1]$-hardness of $\mathsf{pSSS}[\mathbb{Z}]$ was shown) and
[1] (where containment of $\mathsf{pSSS}^{\neq}[\mathbb{Z}]$ in
$\mathsf{W}[3]$ was shown).

Clearly, the problems $\mathsf{pKS}[\mathsf{AbPG}]$ and
$\mathsf{pSSS}[\mathsf{AbPG}]$ are $\mathsf{W}[1]$-hard; this follows from the
corresponding results for $\mathsf{pF}[\mathsf{CycPG}]$ and
$\mathsf{pSSS}[\mathsf{CycPG}]$. The best upper bound that we can show is
$\mathsf{W}[5]$ following the ideas of the proof for
$\mathsf{pSSS}^{\neq}[\mathbb{Z}]\in\mathsf{W}[3]$ from [1]. Details can be
found in Appendix 0.H.

###### Theorem 4.5

The problems $\mathsf{pSSS}[\mathsf{FAbG}]$ and $\mathsf{pKS}[\mathsf{FAbG}]$
belong to $\mathsf{W}[5]$.

##  5 Change making problems

The problem $\mathsf{pKS}_{\leq}[\mathbb{N}]$ (resp.,
$\mathsf{pSSS}_{\leq}^{\neq}[\mathbb{N}]$) was studied in [10] under the name
p-unbounded-change-making (resp., p-0-1-change-making). A third variant from
[10] is:

######  Problem 7 (p-bounded-change-making [10])

Input: binary encoded numbers $c,c_{1},b_{1}\ldots,c_{m},b_{m}\in\mathbb{N}$
with $c_{i}\neq c_{j}$ for $i\neq j$ and $k\in\mathbb{N}$ (the parameter)
Question: Are there $x_{i}\in[0,b_{i}]$ $(i\in[1,m])$ with
$\sum_{i=1}^{m}x_{i}c_{i}=c$ and $\sum_{i=1}^{m}x_{i}\leq k$?

It was shown in [10] that these change-making problems are
$\mathsf{W}[1]$-hard and contained in $\mathsf{XP}$. For p-unbounded-change-
making and p-0-1-change-making we obtain membership in $\mathsf{W}[3]$ from
Theorem 4.4. Also p-bounded-change-making belongs to $\mathsf{W}[3]$. For
this, notice that $\textsf{p-bounded-change-
making}\leq^{\mathsf{fpt}}\mathsf{pSSS}_{\leq}^{\neq}[\mathbb{N}]$: because of
the restriction $\sum_{i=1}^{m}x_{i}\leq k$ in p-bounded-change-making, we can
assume that $b_{i}\leq k$ for all $i\in[1,m]$. We obtain an instance of
$\mathsf{pSSS}_{\leq}[\mathbb{N}]$ by duplicating every $c_{i}$ in a
p-bounded-change-making-instance $b_{i}$ times. On the other hand, we also
have $\mathsf{pKS}_{\leq}[\mathbb{N}]\leq^{\mathsf{fpt}}\textsf{p-bounded-
change-making}$: if we set $b_{i}=k$ for all $i\in[1,m]$ in p-bounded-change-
making, we obtain $\mathsf{pKS}_{\leq}[\mathbb{N}]$. Therefore, we obtain:

###### Theorem 5.1

The problem p-bounded-change-making is equivalent to the problems from Theorem
4.4 and therefore belongs to $\mathsf{W}[3]$.

In [10], approximate versions of the change-making problems, where a linear
objective function is minimized, were defined:

######  Problem 8 (p-unbounded-change-approx [10])

Input: binary encoded numbers $c,c_{1},\dots,c_{m}\in\mathbb{N}$ with
$c_{i}\neq c_{j}$ for $i\neq j$, a linear function $f(x,y)=ax+by$ given by
$a,b\in\mathbb{N}$ and $k\in\mathbb{N}$ (the parameter)
Question: Are there $x_{1},\dots,x_{m}\in\mathbb{N}$ with
$f(\sum_{i=1}^{m}x_{i}c_{i}-c,\sum_{i=1}^{m}x_{i})\leq k$ and
$\sum_{i=1}^{m}x_{i}c_{i}\geq c$?

######  Problem 9 (p-bounded-change-approx [10])

Input: binary encoded numbers $c,c_{1},b_{1}\dots,c_{m},b_{m}\in\mathbb{N}$
with $c_{i}\neq c_{j}$ for $i\neq j$, a linear function $f(x,y)=ax+by$ given
by $a,b\in\mathbb{N}$ and $k\in\mathbb{N}$ (the parameter)
Question: Are there $x_{1},\ldots,x_{m}\in[0,b_{i}]$ with
$f(\sum_{i=1}^{m}x_{i}c_{i}-c,\sum_{i=1}^{m}x_{i})\leq k$ and
$\sum_{i=1}^{m}x_{i}c_{i}\geq c$?

Finally, by fixing all $b_{i}$ to $1$ in p-bounded-change-approx, one obtains
the problem p-0-1-change-approx [10]. Also for the above approximation
variants, $\mathsf{W}[1]$-hardness and containment in XP was shown in [10].
With our results we can improve the upper bounds:

###### Theorem 5.2

The problems $\mathsf{pSSS}[\mathbb{N}]$, p-unbounded-change-approx,
p-bounded-change-approx and p-0-1-change-approx are equivalent under fpt-
reductions when restricted to functions $f(x,y)=ax+by$ with
$(a,b)\in\mathbb{N}\times\mathbb{N}\setminus\\{(a,0)\mid a\geq 1\\}$.
Therefore the problems belong to $\mathsf{W}[3]$.

###### Proof

We only explain the main steps of the proof. A detailed exposition can be
found in Appendix 0.I.1.

We prove the theorem by a sequence of reductions. The only difficult step is
to show p-bounded-change-approx
$\leq^{\mathsf{fpt}}\mathsf{pSSS}_{\leq}[\mathbb{Z}]$ (the latter is
equivalent to $\mathsf{pSSS}[\mathbb{N}]$ by Theorem 4.4).

Let $c,c_{1},b_{1},\dots,c_{m},b_{m},f(x,y)=ax+by$, and $k$ be the input data
for p-bounded-change-approx. If $a=0=b$ or ($a=0$ and $b\geq 1$), one can
directly check in polynomial time whether the p-bounded-change-approx-instance
is positive.

The case that remains is $a,b\geq 1$. We define the following integers:

$\displaystyle d$ $\displaystyle=c\cdot 2^{\\#(ka)+\\#(kb)}$ $\displaystyle
d_{i}$ $\displaystyle=b-1+c_{i}\cdot 2^{\\#(ka)+\\#(kb)}\text{ for }i\in[1,m]$
$\displaystyle d_{0}$ $\displaystyle=-1$ $\displaystyle\qquad d_{m+1}$
$\displaystyle=(1-a)\cdot 2^{\\#(kb)}-2^{\\#(ka)+\\#(kb)}$ $\displaystyle
d_{m+2}$ $\displaystyle=2^{\\#(kb)}$

Moreover, we set $k=b_{0}=b_{m+1}=b_{m+2}$.

###### Claim 3

The p-bounded-change-approx-instance
$c,c_{1},b_{1},\dots,c_{m},b_{m},f(x,y)=ax+by$, $k$ is positive iff there
exist $x_{i}\in[0,b_{i}]$ $(0\leq i\leq m+2)$ such that

$\sum_{i=0}^{m+2}x_{i}d_{i}=d\quad\text{ and }\quad\sum_{i=0}^{m+2}x_{i}\leq
k.$ (7)

First suppose the p-bounded-change-approx-instance is positive. Then there
exist $x_{i}\in[0,b_{i}]$ ($i\in[1,m]$) with

$\sum_{i=1}^{m}x_{i}c_{i}\geq c\quad\text{ and }\quad
a\bigg{(}\sum_{i=1}^{m}x_{i}c_{i}-c\bigg{)}+b\sum_{i=1}^{m}x_{i}\leq k.$

Let $x_{0}=(b-1)\sum_{i=1}^{m}x_{i}$, $x_{m+1}=\sum_{i=1}^{m}x_{i}c_{i}-c$ and
$x_{m+2}=(a-1)(\sum_{i=1}^{m}x_{i}c_{i}-c)$. A simple calculation shows that
(7) holds. Therefore we have $x_{0},x_{m+1},x_{m+2}\in[0,k]$ and thus
$x_{i}\in[0,b_{i}]$ for all $i\in[0,m+2]$.

For the other direction in Claim 3 assume that $x_{i}\in[0,b_{i}]$ are such
that

$\sum_{i=0}^{m+2}x_{i}d_{i}=d\quad\text{ and }\quad\sum_{i=0}^{m+2}x_{i}\leq
k.$ (8)

We bring the left equation in (8) in a form where all numbers are positive:

$\sum_{i=1}^{m}x_{i}d_{i}+x_{m+2}d_{m+2}=d+x_{0}(-d_{0})+x_{m+1}(-d_{m+1}),$

or, after plugging in the values of the $d_{i}$ and rearranging,

$\displaystyle\sum_{i=1}^{m}x_{i}(b-1)$ $\displaystyle\ +\ $ $\displaystyle
x_{m+2}$ $\displaystyle\ 2^{\\#(kb)}$ $\displaystyle\ +\
\bigg{(}\sum_{i=1}^{m}x_{i}c_{i}\bigg{)}$ $\displaystyle\ 2^{\\#(ka)+\\#(kb)}$
$\displaystyle=\ \ $ $\displaystyle x_{0}$ $\displaystyle\ +\ $ $\displaystyle
x_{m+1}(a-1)$ $\displaystyle\ 2^{\\#(kb)}$ $\displaystyle\ +\ (c+x_{m+1})$
$\displaystyle\ 2^{\\#(ka)+\\#(kb)}$

Note that $\sum_{i=1}^{m}x_{i}(b-1)$ and $x_{0}$ are bounded by $kb$ and
therefore have at most $\\#(kb)$ bits. All other terms in the above equation
are multiplied with $2^{\\#(kb)}$ and therefore do not affect the first
$\\#(kb)$ bits. Similarly, $x_{m+2}$ and $x_{m+1}(a-1)$ are bounded by $ka$
and therefore have at most $\\#(ka)$ bits. We therefore can split the above
equation into three simultaneous equations:

$\displaystyle\sum_{i=1}^{m}x_{i}(b-1)$ $\displaystyle=$ $\displaystyle x_{0}$
(9) $\displaystyle x_{m+2}$ $\displaystyle=$ $\displaystyle x_{m+1}(a-1)$ (10)
$\displaystyle\sum_{i=1}^{m}x_{i}c_{i}$ $\displaystyle=$ $\displaystyle
c+x_{m+1}$ (11)

By (11) we have $x_{m+1}=\sum_{i=1}^{m}x_{i}c_{i}-c$. Together with (10) this
gives us $x_{m+2}=(a-1)(\sum_{i=1}^{m}x_{i}c_{i}-c)$. Adding up all variables
and using (9) yields

$\displaystyle k\geq\sum_{i=0}^{m+2}x_{i}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{m}x_{i}(b-1)+\sum_{i=1}^{m}x_{i}+\sum_{i=1}^{m}x_{i}c_{i}-c+(a-1)\bigg{(}\sum_{i=1}^{m}x_{i}c_{i}-c\bigg{)}$
$\displaystyle=$ $\displaystyle
a\bigg{(}\sum_{i=1}^{m}x_{i}c_{i}-c\bigg{)}+b\sum_{i=1}^{m}x_{i}.$

Moreover, since we have $x_{m+1}\geq 0$, (11) finally implies
$\sum_{i=1}^{m}x_{i}c_{i}\geq c$ which proves the claim. ∎

By Claim 3 we obtain an equivalent instance of
$\mathsf{pSSS}_{\leq}[\mathbb{Z}]$ by defining a list where for $i\in[0,m+2]$
the number $d_{i}$ is contained exactly $b_{i}$ times. ∎

For the missing case of a function $f(x,y)=ax+by$ with $a\geq 1$ and $b=0$ we
have:

###### Theorem 5.3

When restricted to $a\geq 1$ and $b=0$, p-unbounded-change-approx, p-bounded-
change-approx and p-0-1-change-approx are para-NP-complete.

We prove the theorem as follows: By [8, Theorem 2.14] a nontrivial
parameterized problem in paraNP is paraNP-complete under fpt-reductions iff
the union of finitely many slices is NP-complete under polynomial time
reductions (the $d^{th}$ slice of a parameterized problem is the restriction
of the problem, where the parameter is set to the fixed value $d$). In
Appendix 0.I.2 we show that already a single slice of the problems from the
theorem is NP-complete under polynomial time reductions.

## References

  * [1] J. F. Buss and T. Islam.  Algorithms in the W-hierarchy.  Theory Comput. Syst., 41(3):445–457, 2007.
  * [2] L. Cai, J. Chen, R. G. Downey, and M. R. Fellows.  On the parameterized complexity of short computation and factorization.  Arch. Math. Log., 36(4-5):321–337, 1997.
  * [3] R. G. Downey and M. R. Fellows.  Parametrized Complexity.  Springer, 1999.
  * [4] R. G. Downey and M. R. Fellows.  Fixed-parameter tractability and completeness II: on completeness for W[1].  Theor. Comput. Sci., 141(1&2):109–131, 1995.
  * [5] S. Even and O. Goldreich.  The minimum-length generator sequence problem is NP-hard.  Journal of Algorithms, 2(3):311–313, 1981.
  * [6] H. Fernau and J. Bruchertseifer.  Synchronizing words and monoid factorization, yielding a new parameterized complexity class?  Mathematical Structures in Computer Science, 32(2):189–215, 2022\.
  * [7] H. Fernau, P. Heggernes, and Y. Villanger.  A multi-parameter analysis of hard problems on deterministic finite automata.  J. Comput. Syst. Sci., 81(4):747–765, 2015.
  * [8] J. Flum and M. Grohe.  Parameterized Complexity Theory.  Springer, 2006.
  * [9] M. L. Furst, J E. Hopcroft, and E. M. Luks.  Polynomial-time algorithms for permutation groups.  In Proc. FOCS 1980, pages 36–41. IEEE Comput. Soc., 1980.
  * [10] S. Goebbels, F. Gurski, J. Rethmann, and E. Yilmaz.  Change-making problems revisited: a parameterized point of view.  J. Comb. Optim., 34(4):1218–1236, 2017.
  * [11] C. S. Iliopoulos.  On the computational complexity of the abelian permutation group structure, membership and intersection problems.  Theor. Comput. Sci., 56:211–222, 1988.
  * [12] M. Jerrum.  The complexity of finding minimum-length generator sequences.  Theor. Comput. Sci., 36:265–289, 1985.
  * [13] M. Lohrey and A. Rosowski.  On the complexity of diameter and related problems in permutation groups.  In Proc. ICALP 2023, volume 261 of LIPIcs, pages 134:1–134:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
  * [14] M. Lohrey, A. Rosowski, and G. Zetzsche.  Membership problems in finite groups.  In Proc. MFCS 2022, volume 241 of LIPIcs, pages 71:1–71:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [15] P. McKenzie and S A. Cook.  The parallel complexity of abelian permutation group problems.  SIAM Journal on Computing, 16(5):880–909, 1987.
  * [16] Á. Seress.  Permutation Group Algorithms.  Cambridge University Press, 2003.
  * [17] P. R. Vaidyanathan.  On the parameterized complexity of permutation group factorization and related problems.  Master’s thesis, IIT Gandhinagar, 2019.

##  Appendix 0.A Additional material for Section 3

###### Theorem 0.A.1

$\mathsf{W}^{\mathsf{func}}[t]=\mathsf{A}^{\mathsf{func}}[1,t]$

###### Proof

It suffices to show

$\mathsf{pMC}(\Sigma^{\mathsf{func}}_{t,u})\leq^{\mathsf{fpt}}\mathsf{pMC}(\Sigma^{\mathsf{func}}_{t,1}).$

Let $\sigma$ be a vocabulary, $\mathcal{A}$ be a $\sigma$-structure and $A$ be
the universe. Furthermore let

$\psi=\exists x_{1}\cdots\exists x_{v}\forall y_{1,1}\cdots\forall
y_{1,u_{1}}\exists y_{2,1}\cdots\exists y_{2,u_{2}}\cdots
Q_{t-1}y_{t-1,1}\cdots Q_{t-1}y_{t-1,u_{t-1}}\varphi$

be a $\Sigma^{\mathsf{func}}_{t,u}$-formula, in which $u_{i}\leq u$ and
$\varphi$ is quantifier-free and $Q_{i}\neq Q_{i+1}$ are alternating
quantifiers. We define a new vocabulary
$\sigma^{\prime}=\sigma\cup\\{\alpha,\pi_{1},\dots,\pi_{u}\\}$ in which
$\alpha$ is a unary relation symbol and the $\pi_{i}$ are unary function
symbols. In the following, for a relation symbol $\rho$ we write
$\rho^{\mathcal{A}}$ (resp., $\rho^{\mathcal{A}^{\prime}}$) for the
interpretation of $\rho$ in the structure $\mathcal{A}$ (resp.,
$\mathcal{A}^{\prime}$). We define a $\sigma^{\prime}$-structure
$\mathcal{A^{\prime}}$ with the universe $A^{\prime}=A^{u}\cup A$ and for
every symbol $S\in\sigma$ we define
$S^{\mathcal{A^{\prime}}}=S^{\mathcal{A}}$. Moreover
$\alpha^{\mathcal{A^{\prime}}}=A$ and for $i\in[1,u]$

$\pi_{i}^{\mathcal{A^{\prime}}}(a)=\begin{cases}a&\text{if }a\in A,\\\
a_{i}&\text{if }a=(a_{1},\dots,a_{u})\in A^{u}.\end{cases}$

Now we define the $\Sigma^{\mathsf{func}}_{t,1}$-formula

$\psi^{\prime}=\exists x_{1}\cdots\exists x_{v}\forall y_{1}\exists
y_{2}\cdots Q_{t-1}y_{t-1}\bigwedge_{i=1}^{v}\alpha
x_{i}\wedge\bigwedge_{i=1}^{\lfloor\frac{t-1}{2}\rfloor}\neg\alpha
y_{2i}\wedge\left(\bigwedge_{i=1}^{\lfloor\frac{t}{2}\rfloor}\neg\alpha
y_{2i-1}\rightarrow\varphi^{\prime}\right)$

in which $\varphi^{\prime}$ is the quantifier-free formula that is obtained
from $\varphi$ by replacing every variable $y_{i,j}$ by $\pi_{j}(y_{i})$. Then
we obtain $\mathcal{A}\models\psi$ if and only if
$\mathcal{A^{\prime}}\models\psi^{\prime}$. ∎

##  Appendix 0.B Proof of Lemma 1.

We only show
$\mathsf{pF}[\mathsf{C}]\leq^{\mathsf{fpt}}\mathsf{pKS}[\mathsf{C}]\leq^{\mathsf{fpt}}\mathsf{pSSS}[\mathsf{C}]$;
the second statement can be shown in the same way. For
$\mathsf{pF}[\mathsf{C}]\leq^{\mathsf{fpt}}\mathsf{pKS}[\mathsf{C}]$ consider
input data $M\in\mathsf{C}$, $a,a_{1},\dots,a_{m}\in M$ and $k\in\mathbb{N}$
for $\mathsf{pF}[\mathsf{C}]$. We clearly have
$a\in\\{a_{1},\dots,a_{m}\\}^{k}$ if and only if there exist
$x_{i,j}\in\mathbb{N}$ ($i\in[1,k]$, $j\in[1,m]$) such that

$a=\prod_{i=1}^{k}\prod_{j=1}^{m}a_{j}^{x_{i,j}}\text{ and
}\sum_{i=1}^{k}\sum_{j=1}^{m}x_{i,j}=k.$ (12)

To show that
$\mathsf{pKS}[\mathsf{C}]\leq^{\mathsf{fpt}}\mathsf{pSSS}[\mathsf{C}]$ note
that there exist $x_{1},\ldots,x_{m}\in\mathbb{N}$ such that

$a=a_{1}^{x_{1}}a_{2}^{x_{2}}\cdots a_{m}^{x_{m}}\text{ and
}\sum_{i=1}^{m}x_{i}=k$

if and only if there exist $x_{i,j}\in\\{0,1\\}$ ($i\in[1,m]$, $j\in[1,k]$)
such that

$a=a_{1}^{x_{1,1}}\cdots a_{1}^{x_{1,k}}a_{2}^{x_{2,1}}\cdots
a_{2}^{x_{2,k}}\cdots a_{m}^{x_{m,1}}\cdots a_{m}^{x_{m,k}}\text{ and
}\sum_{i=1}^{m}\sum_{j=1}^{k}x_{i,j}=k.$

This shows Lemma 1. ∎

##  Appendix 0.C Proof of Theorem 4.1

We present an fpt-reduction from $\mathsf{pF}[\mathsf{T}_{*}]$ to
$\mathsf{pMC}(\Sigma_{2,1}^{\mathsf{func}})$. Consider an input instance
$(f,B,k)$ for $\mathsf{pF}[\mathsf{T}_{*}]$, where $f\in T_{n}$, $B\subseteq
T_{n}$ and $k\in\mathbb{N}$. W.l.o.g. we can assume that $B$ contains the
identity function $\mathrm{id}$ with $\mathrm{id}(a)=a$ for all $a\in[1,n]$.
Then, $(f,B,k)$ is a positive instance of $\mathsf{pF}[\mathsf{T}_{*}]$ if and
only if there are $f_{1},\dots,f_{k}\in B$ such that $a^{f}=a^{f_{1}\cdots
f_{k}}$ for all $a\in[1,n]$. Let $\sigma=\\{P,Q,h\\}$ be a vocabulary in which
$P$ is a unary relation symbol, $Q$ is a binary relation symbol, and $h$ is a
binary function symbol. We define the $\sigma$-structure $\mathcal{A}$ as
follows:

  * •

$A=[1,n]\uplus B$ is the universe,

  * •

$P^{\mathcal{A}}=B$,

  * •

$Q^{\mathcal{A}}=\\{(a,af)\mid a\in[1,n]\\}\cup(B\times B)$ and

  * •

the interpretation of the function symbol $h$ is defined as follows, where
$g\in B$ is arbitrary:

$h^{\mathcal{A}}(a,p)=\begin{cases}ap&\text{if }a\in[1,n]\text{ and }p\in
B,\\\ g&\text{if }a\in B\text{ or }p\in[1,n].\\\ \end{cases}$

Let $\varphi_{k}$ be the $\Sigma_{2,1}^{\mathsf{func}}$-formula

$\varphi_{k}=\exists x_{1}\cdots\exists
x_{k}\bigwedge_{i=1}^{k}P(x_{i})\wedge\forall z\;Q(z,h(\ldots
h(h(z,x_{1}),x_{2}),\ldots,x_{k})).$

Then $(f,B,k)$ is a positive instance if and only if
$\mathcal{A}\models\varphi_{k}$. ∎

##  Appendix 0.D Proof of Theorem 4.3

Let $B\subseteq S_{n}$ be a set of permutations and let $k\in\mathbb{N}$ be
the parameter of an instance of $\mathsf{p\text{-}Diameter}$. W.l.o.g. we can
assume that the identity permutation $\mathrm{id}$ belongs to $B$. Then we
have $d(B)>k$ if and only if there are generators $\pi_{1},\dots,\pi_{k+1}\in
B$ such that for all generators $\tau_{1},\dots,\tau_{k}\in B$ there is
$i\in[1,n]$ such that

$i\cdot\pi_{1}\cdots\pi_{k+1}\neq i\cdot\tau_{1}\cdots\tau_{k}.$

Let $\sigma=\\{P,Q,h\\}$ be a vocabulary in which $P$ is a unary relation
symbol, $Q$ is a binary relation symbol, and $h$ is a binary function symbol.
Now we define the $\sigma$-structure $\mathcal{A}$:

  * •

$A=B\uplus[1,n]$ is the universe,

  * •

$P^{\mathcal{A}}=B$,

  * •

$Q^{\mathcal{A}}=\\{(a,b)\mid a,b\in[1,n],a\neq b\\}$, and

  * •

the interpretation of the function symbol $h$ is defined as follows, where
$g\in B$ is arbitrary:

$h^{\mathcal{A}}(a,p)=\begin{cases}ap&\text{if }a\in[1,n]\text{ and }p\in
B,\\\ g&\text{if }a\in B\text{ or }p\in[1,n].\end{cases}$

Next we define the sentence

$\displaystyle\varphi_{k}$ $\displaystyle=\exists x_{1}\cdots\exists
x_{k+1}\bigwedge_{i=1}^{k+1}P(x_{i})\wedge\forall y_{1}\cdots\forall
y_{k}\bigwedge_{i=1}^{k}P(y_{i})\rightarrow$
$\displaystyle\quad\qquad\qquad\qquad\exists z\;Q(h(\cdots
h(h(z,x_{1}),x_{2}),\ldots,x_{k+1}),h(\cdots
h(h(z,y_{1}),y_{2}),\ldots,y_{k})).$

Note that $|\varphi_{k}|\in\mathcal{O}(k)$. Then obviously $d(B)>k$ holds if
and only if $\mathcal{A}\models\varphi_{k}$. ∎

##  Appendix 0.E Simple lemmas

In this section, we collect a few simple lemmas that will be needed for the
proof of Theorem 4.4.

Clearly, the $\mathbb{N}$-variants of our factorization problems reduce to the
corresponding $\mathbb{Z}$-variants. Vice versa, by adding a large enough
element from $\mathbb{N}$ (resp., $\mathbb{N}^{*}$) to all input elements, one
gets:

###### Lemma 2

For all $\mathsf{X}\in\\{\mathsf{KS},\mathsf{SSS},\mathsf{SSS}^{\neq}\\}$ we
have $\mathsf{pX}[\mathbb{Z}]\leq^{\mathsf{fpt}}\mathsf{pX}[\mathbb{N}]$ and
$\mathsf{pX}[\mathbb{Z}^{*}]\leq^{\mathsf{fpt}}\mathsf{pX}[\mathbb{N}^{*}]$.

###### Proof

Consider input vectors $a,a_{1},\ldots,a_{m}\in\mathbb{Z}^{d}$ and let $k\geq
1$ be the parameter. All integers are given in binary representation. We then
compute a vector $b\in\mathbb{N}^{d}$ such that
$a+kb,a_{1}+b,\ldots,a_{m}+b\in\mathbb{N}^{d}$ and take the new input elements
$a+kb,a_{1}+b,\ldots,a_{m}+b$. ∎

The next lemma is shown by concatenating the binary representations of $d$
integers $c_{1},\ldots,c_{d}$ to a single binary representation with enough
zeros inbetween in order to avoid unwanted carries.

###### Lemma 3

For all
$\mathsf{X}\in\\{\mathsf{KS},\mathsf{KS}_{\leq},\mathsf{SSS},\mathsf{SSS}_{\leq},\mathsf{SSS}^{\neq},\mathsf{SSS}^{\neq}_{\leq}\\}$
we have
$\mathsf{pX}[\mathbb{N}^{*}]\leq^{\mathsf{fpt}}\mathsf{pX}[\mathbb{N}]$.

###### Proof

We only show
$\mathsf{pSSS}^{\neq}[\mathbb{N}^{*}]\leq^{\mathsf{fpt}}\mathsf{pSSS}^{\neq}[\mathbb{N}]$,
the reduction also works for the other cases. Let $A\subseteq\mathbb{N}^{d}$,
$a\in\mathbb{N}^{d}$ and $k\geq 1$ be the input data for
$\mathsf{pSSS}^{\neq}[\mathbb{N}^{*}]$. Every number is given in binary
representation.

The idea is then to append the binary representations of $d$ integers
$c_{1},\ldots,c_{d}$ into a single binary representation with enough zeros
inbetween in order to avoid unwanted carries. Let $e$ be the maximum entry in
a vector from $A$ and let $m=\\#(ke)$. W.l.o.g. we can assume that all entries
in the vector $a$ are bounded by $ke$.

Consider a tuple $c=(c_{1},\ldots,c_{d})\in[0,ke]^{d}$ and let $(b_{i,1}\cdots
b_{i,m_{i}})$ be the binary representation of the number $c_{i}$ with
$b_{i,1}$ the least significant bit. Note that $b_{i,m_{i}}=1$ and $m_{i}\leq
m$. We then encode $c$ by the number $\mathsf{code}(c)$ with the binary
representation

$(b_{1,1}\cdots b_{1,m_{1}}\\!\\!\\!\\!\underbrace{00\cdots
0}_{\text{$m-m_{1}$ many}}\\!\\!\\!\\!b_{2,1}\cdots
b_{2,m_{2}}\\!\\!\\!\\!\underbrace{00\cdots 0}_{\text{$m-m_{2}$
many}}\\!\\!\\!\\!\cdots b_{d,1}\cdots b_{d,m_{d}}).$

Let $\mathsf{code}(A)=\\{\mathsf{code}(b):b\in A\\}$. Then, there is a subset
$S\subseteq A$ of size $k$ such that $\sum_{b\in S}b=a$ if and only if there
is a subset $S\subseteq\mathsf{code}(A)$ of size $k$ such that $\sum_{b\in
S}b=\mathsf{code}(a)$. ∎

In [17] it was shown that $\mathsf{pF}[\mathsf{S}_{*}]$ and
$\mathsf{pF}_{\leq}[\mathsf{S}_{*}]$ are equivalent with respect to fpt-
reductions. One direction generalizes easily to the following statement
(simply add the neutral element $1$ sufficiently many times to the input
list):

###### Lemma 4

For all classes $\mathsf{C}$ and
$\mathsf{X}\in\\{\mathsf{F},\mathsf{KS},\mathsf{SSS}\\}$ we have
$\mathsf{pX_{\leq}[C]}\leq\mathsf{pX[C]}$.

###### Proof

For $\mathsf{X}\in\\{\mathsf{F},\mathsf{KS}\\}$ it suffices to add the neutral
element $1\in M$ to the input sequence $a_{1},\ldots,a_{m}$. For
$\mathsf{pSSS}_{\leq}[\mathsf{C}]\leq^{\mathsf{fpt}}\mathsf{pSSS}[\mathsf{C}]$,
we have to add $k$ copies of $1$ to the input sequence. ∎

###### Lemma 5

If
$\mathsf{X}\in\\{\mathsf{F},\mathsf{KS},\mathsf{SSS},\mathsf{SSS}^{\neq}\\}$
and $\mathsf{C}$ is one of the classes from Definition 1 except for
$\mathsf{C}=\mathsf{FCycG}$, then
$\mathsf{pX[C]}\leq^{\mathsf{fpt}}\mathsf{pX_{\leq}[C]}$.

###### Proof

Let us explain the idea for
$\mathsf{pF}[\mathsf{S}_{*}]\leq^{\mathsf{fpt}}\mathsf{pF}_{\leq}[\mathsf{S}_{*}]$
and consider the symmetric group $S_{n}$ and the elements
$\pi,\pi_{1},\ldots,\pi_{m}\in S_{n}$. The idea is to work in the group
$S_{n}\times\mathbb{Z}_{k+1}\leq S_{n+k+1}$. For this take for $\tau$ a cycle
of length $k+1$ on the set $[n+1,n+k+1]$ and view $\pi,\pi_{1},\dots,\pi_{m}$
as elements of $S_{n+k+1}$. Then we have
$\pi\in\\{\pi_{1},\ldots,\pi_{m}\\}^{k}$ if and only if
$\pi\tau^{k}\in\\{\pi_{1}\tau,\ldots,\pi_{m}\tau\\}^{\leq k}$. The same idea
works (with small modifications) for the classes $\mathsf{T}_{*}$,
$\mathsf{CycPG}$, $\mathsf{AbPG}$, $\mathsf{FAbG}$, $\mathbb{Z}^{*}$, and
$\mathbb{N}^{*}$. For $\mathsf{CycPG}$ we have to take a cycle of length
$p>\max(n,k)$ for a prime $p$ instead of the cycle $\tau$ of length $k+1$.
Since $n$ is given in unary notation, such a prime can be found in polynomial
time. Then, for every $\pi\in S_{n}$, the group
$\langle\pi\rangle\times\langle\tau\rangle$ is again cyclic and the cycle
$\tau$ has length at least $k+1$. Finally, for $\mathbb{Z}$ we first reduce
$\mathsf{pX[\mathbb{Z}]}$ to $\mathsf{pX[\mathbb{N}]}$ using Lemma 2. The
latter is then reduced to $\mathsf{pX_{\leq}[\mathbb{N}\times\mathbb{N}]}$
using the above construction. Finally
$\mathsf{pX_{\leq}[\mathbb{N}\times\mathbb{N}]}$ can be reduced to
$\mathsf{pX_{\leq}[\mathbb{N}]}$ by Lemma 3. ∎

###### Lemma 6

We have
$\mathsf{pSSS}[\mathsf{C}]\leq^{\mathsf{fpt}}\mathsf{pSSS}^{\neq}[\mathsf{C}]$
for each of the classes from Definition 1 except for
$\mathsf{C}=\mathsf{FCycG}$.

###### Proof

We first show
$\mathsf{pSSS}[\mathsf{S}_{*}]\leq^{\mathsf{fpt}}\mathsf{pSSS}^{\neq}[\mathsf{S}_{*}]$.
Consider input data $\pi,\pi_{1},\ldots,\pi_{m}\in S_{n}$ and $k$ for
$\mathsf{pSSS}[\mathsf{S}_{*}]$. We will work with the group
$\mathbb{Z}_{2}^{2m+1}\times\mathbb{Z}_{2k+2}\times S_{n}\leq S_{4m+2k+n+4}$.

Consider $i\in[1,m]$. We replace the element $\pi_{i}$ in the sequence
$\pi_{1},\ldots,\pi_{m}$ by the group element

$\rho_{i}=(e^{2m+1}_{2i},1,\pi_{i})\in\mathbb{Z}_{2}^{2m+1}\times\mathbb{Z}_{2k+2}\times
S_{n},$

where $e^{2m+1}_{2i}\in\mathbb{Z}_{2}^{2m+1}$ is the $2m+1$ dimensional unit
vector with a $1$ at the $(2i)^{th}$ coordinate (all other entries are zero).
Note that the $\rho_{i}$ are pairwise different. We then add to the sequence
all “filling elements”

$(0,\ldots,0,1,\ldots,1,0,\ldots,0,\mathsf{id})\in\mathbb{Z}_{2}^{2m+1}\times\mathbb{Z}_{2k+2}\times
S_{n}$ (13)

where the $1$’s form a contiguous non-empty block that starts at some position
$2i+1$ and ends at some position $2j+1$ with $0\leq i\leq j\leq m$. With
$\mathsf{id}$ we denote the identity permutation on $[1,n]$. Let
$\rho_{m+1},\ldots,\rho_{m+\ell}$ be a list of all filling elements (the
precise order does not matter, since the filling elements pairwise commute).
Note that the elements in the list $\rho_{1},\ldots,\rho_{m+\ell}$ are
pairwise different.

Finally, let
$\rho=(1,1,\ldots,1,k,\pi)\in\mathbb{Z}_{2}^{2m+1}\times\mathbb{Z}_{2k+2}\times
S_{n}$. We claim that there is a subset $I\subseteq[1,m]$ such that $|I|=k$
and $\prod_{i\in I}\pi_{i}=\pi$ if and only if there is a subset
$J\subseteq[1,m+\ell]$ with $|J|=2k+1$ and $\prod_{j\in
J}\rho_{j}=\rho$.222When writing $\prod_{i\in I}\pi_{i}$ we assume that the
product goes over the set $I$ in ascending order and similarly for other
products.

First assume that there is $J\subseteq[1,m+\ell]$ with $|J|=2k+1$ and
$\prod_{j\in J}\rho_{j}=\rho$. The $k$ in the second last position of $\rho$
forces $J$ to contain exactly $k$ indices from $[1,m]$. Let $I=J\cap[1,m]$ so
that $|I|=k$. Projecting on the last coordinate yields $\prod_{i\in
I}\pi_{i}=\pi$.

For the other direction let $I\subseteq[1,m]$ with $|I|=k$ and $\prod_{i\in
I}\pi_{i}=\pi$. Consider now the group element $\prod_{i\in I}\rho_{i}$. Its
last entry is $\pi$ and the second last entry is $k$. Moreover, the first
$2m+1$ entries of $\prod_{i\in I}\rho_{i}$ contain exactly $k$ ones (all other
entries are zero) and two ones are separated by at least one zero. The zero
gaps can be filled with exactly $k+1$ filling elements of the form (13).
Hence, there is a subset $J\subseteq[m+1,m+\ell]$ such that $\prod_{i\in I\cup
J}\rho_{i}=\rho$.

The same reduction can be used in a similar way for the other classes from
Definition 1 except for $\mathsf{C}=\mathsf{FCycG}$. For
$\mathsf{C}=\mathsf{CycPG}$ we replace the cyclic permutation group $G\leq
S_{n}$ by $\prod_{i=1}^{2m+2}\mathbb{Z}_{p_{i}}\times G$, where
$p_{1}<p_{2}<\cdots<p_{2m+2}$ are primes with $p_{1}\geq\max\\{n+1,2k+2\\}$.
This ensures that $\prod_{i=1}^{2m+2}\mathbb{Z}_{p_{i}}\times G\leq
S_{n^{\prime}}$ is again a cyclic permutation group with
$n^{\prime}=\sum_{i=1}^{2m+2}p_{i}+n$.

Finally for $\mathsf{C}=\mathbb{Z}$ and $\mathsf{C}=\mathbb{N}$ we obtain with
Lemmas 2 and 3 the following reduction:
$\mathsf{pSSS}[\mathbb{N}]\leq^{\mathsf{fpt}}\mathsf{pSSS}[\mathbb{Z}]\leq^{\mathsf{fpt}}\mathsf{pSSS}[\mathbb{Z}^{*}]\leq^{\mathsf{fpt}}\mathsf{pSSS}^{\neq}[\mathbb{Z}^{*}]\leq^{\mathsf{fpt}}\mathsf{pSSS}^{\neq}[\mathbb{N}^{*}]\leq^{\mathsf{fpt}}\mathsf{pSSS}^{\neq}[\mathbb{N}]\leq^{\mathsf{fpt}}\mathsf{pSSS}^{\neq}[\mathbb{Z}]$.
∎

Note that for a cyclic group $\mathbb{Z}_{n}$ with $n$ given in binary
representation, we would have to find a prime $p>n$ in the proofs of Lemmas 5
and 6. Since $n$ is given in binary representation, there is no polynomial
time algorithm known for this problem (although it is generally expected that
such an algorithm exists). Nevertheless, the statements of Lemmas 5 and 6 also
hold for $\mathsf{C}=\mathsf{FCycG}$; this will be shown later (see Theorem
4.4).

###### Corollary 2

Let $\mathsf{C}$ be one of the classes from Definition 1 except for
$\mathsf{C}=\mathsf{FCycG}$. Then the problems $\mathsf{pSSS}[\mathsf{C}]$,
$\mathsf{pSSS}^{\neq}[\mathsf{C}]$, $\mathsf{pSSS}_{\leq}[\mathsf{C}]$,
$\mathsf{pSSS}_{\leq}^{\neq}[\mathsf{C}]$ are equivalent with respect to fpt-
reductions.

###### Proof

By Lemmas 4 and 5, we have
$\mathsf{pSSS}[\mathsf{C}]\equiv^{\mathsf{fpt}}\mathsf{pSSS}_{\leq}[\mathsf{C}]$.
By Lemma 6 we have
$\mathsf{pSSS}[\mathsf{C}]\equiv^{\mathsf{fpt}}\mathsf{pSSS}^{\neq}[\mathsf{C}]$
($\mathsf{pSSS}^{\neq}[\mathsf{C}]\leq^{\mathsf{fpt}}\mathsf{pSSS}[\mathsf{C}]$
is trivial). Moreover, we have

$\mathsf{pSSS}_{\leq}^{\neq}[\mathsf{C}]\leq^{\mathsf{fpt}}\mathsf{pSSS}_{\leq}[\mathsf{C}]\leq^{\mathsf{fpt}}\mathsf{pSSS}[\mathsf{C}]\leq^{\mathsf{fpt}}\mathsf{pSSS}^{\neq}[\mathsf{C}]\leq^{\mathsf{fpt}}\mathsf{pSSS}_{\leq}^{\neq}[\mathsf{C}],$

where the final reduction follows from Lemma 5. ∎

For $\mathsf{C}=\mathsf{FCycG}$ we will show the conclusion of Coroallary 2
later (see Corollary 3 below).

##  Appendix 0.F Proof of Theorem 4.4

###### Lemma 7

For all
$\mathsf{X}\in\\{\mathsf{KS},\mathsf{KS}_{\leq},\mathsf{SSS},\mathsf{SSS}_{\leq},\mathsf{SSS}^{\neq},\mathsf{SSS}^{\neq}_{\leq}\\}$
we have

$\mathsf{pX}[\mathsf{AbPG}]\leq^{\mathsf{fpt}}\mathsf{pX}[\mathsf{FAbG}]\quad\text{
and
}\quad\mathsf{pX}[\mathsf{CycPG}]\leq^{\mathsf{fpt}}\mathsf{pX}[\mathsf{FCycG}].$

This result is an immediate consequence of the following result from [11, 15]:

######  Theorem 0.F.1 (c.f. [11, 15])

From a list $\pi_{1},\ldots,\pi_{m}\in S_{n}$ of pairwise commuting
permutations one can compute in polynomial time the following:

  * •

binary encoded numbers $n_{1},\ldots,n_{d}$ such that
$\langle\pi_{1},\ldots,\pi_{m}\rangle\cong\prod_{j=1}^{d}\mathbb{Z}_{n_{j}}$
and

  * •

an isomorphism
$h:\langle\pi_{1},\ldots,\pi_{m}\rangle\to\prod_{i=1}^{d}\mathbb{Z}_{n_{i}}$
that is represented by $h(\pi_{1}),\ldots h(\pi_{m})$.

For the proof of Theorem 4.4 we will only need the case of Theorem 0.F.1 for
cyclic permutation groups. For this case, we provide a self-contained proof in
Appendix 0.G below.

###### Lemma 8

$\mathsf{pSSS}[\mathsf{FCycG}]\leq^{\mathsf{fpt}}\mathsf{pSSS}[\mathbb{Z}^{*}]$

###### Proof

Let $\mathbb{Z}_{n}$ be the input group with $n$ given in binary
representation and let $a,a_{1},\ldots,a_{m}\in[0,n-1]$ be the input elements.

We have to check whether there exists a subset $I\subseteq[1,m]$ such that
$|I|=k$ and

$\sum_{i\in I}a_{i}\equiv a\mod n.$ (14)

For every $I\subseteq[1,m]$ of size $k$, (14) is equivalent to

$\exists q\in[0,k]:\sum_{i\in I}a_{i}-q\cdot n=a.$ (15)

We define $a^{\prime}=(k,a)$, $a^{\prime}_{i}=(1,a_{i})$ and $b=(0,-n)$. These
are elements of $\mathbb{Z}^{2}$. Let us consider the sequence
$(a^{\prime}_{1},a^{\prime}_{2}\ldots,a^{\prime}_{m},b,\ldots,b)$ of length
$m+k$, where $b$ appears exactly $k$ times. Write this sequence as
$(c_{1},c_{2},\ldots,c_{m+k})$. Then there is $I\subseteq[1,m]$ such that
$|I|=k$ and (15) holds, if and only if there is a subset $J\subseteq[1,m+k]$
such that $|J|\leq 2k$ and

$\sum_{j\in J}c_{j}=a^{\prime}.$ (16)

Finally, by adding the zero vector $2k$ times to the sequence
$(c_{1},c_{2},\ldots,c_{m+k})$, we can replace the condition $|J|\leq 2k$ by
the condition $|J|=2k$. ∎

###### Lemma 9

$\mathsf{pSSS}[\mathbb{N}]\leq^{\mathsf{fpt}}\mathsf{pSSS}[\mathsf{CycPG}]$

###### Proof

The result is an easy consequence of the Chinese remainder theorem. Let
$a,a_{1},\dots,a_{m}\in\mathbb{N}$ and $k\in\mathbb{N}$ be the input data for
$\mathsf{pSSS}[\mathbb{N}]$. Let $e=\max\\{a_{1},\dots,a_{m}\\}$ and $d$ be
the smallest number such that

$\prod_{i=1}^{d}p_{i}>ke,$

where $p_{1}<\dots<p_{d}$ are the first $d$ primes. We have
$d\leq\mathcal{O}(\log k+\log e)$ and $p_{d}\leq\mathcal{O}(d\log d)$. The
list $p_{1},\ldots,p_{d}$ with every $p_{i}$ in unary encoding can be computed
in time $\operatorname{poly}(\log k,\log e)$.

Note that our $\mathsf{pSSS}[\mathbb{N}]$-instance has no solution if $a>ke$.
In this case the reduction returns some negative
$\mathsf{pSSS}[\mathsf{CycPG}]$-instance. Hence we can assume that $a\leq ke$
in the following.

The group we are working with is $G=\prod_{i=1}^{d}\mathbb{Z}_{p_{i}}$. Since
the primes are chosen pairwise different, the group $G$ is isomorphic to the
cyclic group $\mathbb{Z}_{N}$ with $N=\prod_{i=1}^{d}p_{i}$. The group $G$ can
be embedded into $S_{n}$ for $n=\sum_{i=1}^{d}p_{i}$ by identifying the direct
factors $\mathbb{Z}_{p_{i}}$ of $G$ with disjoint cycles of length $p_{i}$
($i\in[1,d]$). For $i\in[1,m]$ and $j\in[1,d]$ let

$z_{i,j}=a_{i}\bmod p_{j}\in[0,p_{j}-1]\ \text{ and }\ z_{j}=a\bmod
p_{j}\in[0,p_{j}-1].$

Then, for every subset $I\subseteq[1,m]$ of size $k$ we have $\sum_{i\in
I}a_{i}=a$ if and only if $\sum_{i\in I}z_{i,j}\equiv z_{j}\mod p_{j}$ for all
$j\in[1,d]$. ∎

###### Corollary 3

All problems $\mathsf{pX}[\mathsf{C}]$ for

  * •

$\mathsf{X}\in\\{\mathsf{SSS},\mathsf{SSS}_{\leq},\mathsf{SSS}^{\neq},\mathsf{SSS}^{\neq}_{\leq}\\}$
and

  * •

$\mathsf{C}\in\\{\mathsf{CycPG},\mathsf{FCycG},\mathbb{N},\mathbb{Z},\mathbb{N}^{*},\mathbb{Z}^{*}\\}$

are equivalent with respect to fpt-reductions.

###### Proof

We have

$\displaystyle\mathsf{pSSS}[\mathsf{CycPG}]\quad$
$\displaystyle\leq^{\mathsf{fpt}}\quad\mathsf{pSSS}[\mathsf{FCycG}]$ (Lemma 7)
(17) $\displaystyle\leq^{\mathsf{fpt}}\quad\mathsf{pSSS}[\mathbb{Z}^{*}]$
(Lemma 8) $\displaystyle\leq^{\mathsf{fpt}}\quad\mathsf{pSSS}[\mathbb{N}^{*}]$
(Lemma 2) $\displaystyle\leq^{\mathsf{fpt}}\quad\mathsf{pSSS}[\mathbb{N}]$
(Lemma 3)
$\displaystyle\leq^{\mathsf{fpt}}\quad\mathsf{pSSS}[\mathsf{CycPG}].$ (Lemma
9) (18)

It remains to show that the problems
$\mathsf{pSSS}[\mathsf{C}],\mathsf{pSSS}^{\neq}[\mathsf{C}],\mathsf{pSSS}_{\leq}[\mathsf{C}],\mathsf{pSSS}_{\leq}^{\neq}[\mathsf{C}]$
are equivalent with respect to fpt-reductions for every
$\mathsf{C}\in\\{\mathsf{CycPG},\mathsf{FCycG},\mathbb{N},\mathbb{Z},\mathbb{N}^{*},\mathbb{Z}^{*}\\}$.
Corollary 2 covers the case
$\mathsf{C}\in\\{\mathsf{CycPG},\mathbb{N},\mathbb{Z},\mathbb{N}^{*},\mathbb{Z}^{*}\\}$.

Finally, for the class $\mathsf{FCycG}$ we can argue as follows:

$\displaystyle\mathsf{pSSS}[\mathsf{FCycG}]\quad$
$\displaystyle\leq^{\mathsf{fpt}}\quad\mathsf{pSSS}[\mathsf{CycPG}]$ see (17)
and (18) above)
$\displaystyle\leq^{\mathsf{fpt}}\quad\mathsf{pSSS}^{\neq}[\mathsf{CycPG}]$
(Lemma 6)
$\displaystyle\leq^{\mathsf{fpt}}\quad\mathsf{pSSS}^{\neq}[\mathsf{FCycG}]$
(Lemma 7) $\displaystyle\leq^{\mathsf{fpt}}\quad\mathsf{pSSS}[\mathsf{FCycG}]$
$\displaystyle\qquad\text{(trivial)}.$

Similarly, we have

$\displaystyle\mathsf{pSSS}[\mathsf{FCycG}]\quad$
$\displaystyle\leq^{\mathsf{fpt}}\quad\mathsf{pSSS}[\mathsf{CycPG}]$ see (17)
and (18) above)
$\displaystyle\leq^{\mathsf{fpt}}\quad\mathsf{pSSS}_{\leq}[\mathsf{CycPG}]$
(Lemma 5)
$\displaystyle\leq^{\mathsf{fpt}}\quad\mathsf{pSSS}_{\leq}[\mathsf{FCycG}]$
(Lemma 7) $\displaystyle\leq^{\mathsf{fpt}}\quad\mathsf{pSSS}[\mathsf{FCycG}]$
$\displaystyle\qquad\text{(Lemma~{}\ref{lemma-simple1})}.$

In the same way we finally get

$\displaystyle\mathsf{pSSS}[\mathsf{FCycG}]\quad$
$\displaystyle\leq^{\mathsf{fpt}}\quad\mathsf{pSSS}[\mathsf{CycPG}]$ see (17)
and (18) above)
$\displaystyle\leq^{\mathsf{fpt}}\quad\mathsf{pSSS}_{\leq}^{\neq}[\mathsf{CycPG}]$
(Lemma 6 followed by Lemma 5)
$\displaystyle\leq^{\mathsf{fpt}}\quad\mathsf{pSSS}_{\leq}^{\neq}[\mathsf{FCycG}]$
(Lemma 7)
$\displaystyle\leq^{\mathsf{fpt}}\quad\mathsf{pSSS}_{\leq}[\mathsf{FCycG}]$
(trivial) $\displaystyle\leq^{\mathsf{fpt}}\quad\mathsf{pSSS}[\mathsf{FCycG}]$
$\displaystyle\qquad\text{(Lemma~{}\ref{lemma-simple1})}.$

This concludes the proof of the corollary. ∎

The missing piece in the proof of Theorem 4.4 from the main part of the paper
is the following:

###### Theorem 0.F.2

If $\mathsf{C}$ is one of the commutative classes from Definition 1 then
$\mathsf{pSSS}[\mathsf{C}]\leq^{\mathsf{fpt}}\mathsf{pKS}_{\leq}[\mathsf{C}]\leq^{\mathsf{fpt}}\mathsf{pKS}_{\leq}[\mathsf{C}]\leq^{\mathsf{fpt}}\mathsf{pKS}[\mathsf{C}]\leq^{\mathsf{fpt}}\mathsf{pSSS}[\mathsf{C}]$.

###### Proof

The statement
$\mathsf{pKS}_{\leq}[\mathsf{C}]\leq^{\mathsf{fpt}}\mathsf{pKS}[\mathsf{C}]\leq^{\mathsf{fpt}}\mathsf{pSSS}[\mathsf{C}]$
holds for every class $\mathsf{C}$ by Lemmas 1 and 4. It remains to show
$\mathsf{pSSS}[\mathsf{C}]\leq^{\mathsf{fpt}}\mathsf{pKS}_{\leq}[\mathsf{C}]$.
The idea is similar to the proof of Lemma 6. It suffices to show
$\mathsf{pSSS}^{\neq}[\mathsf{C}]\leq^{\mathsf{fpt}}\mathsf{pKS}_{\leq}[\mathsf{C}]$.
We first prove the theorem for $\mathsf{C}=\mathbb{Z}^{*}$.

Let $A\subseteq\mathbb{Z}^{n}$ be finite, $a\in\mathbb{Z}^{n}$ and $k$ be the
parameter. Let $A=\\{a_{1},\ldots,a_{m}\\}$. We then move to the group
$\mathbb{Z}^{m+n+1}$. For $i\in[1,m]$ let $e_{i}\in\mathbb{Z}^{m}$ be the
$i^{th}$ unit vector, i.e., the vector with $m$ entries, where the $i^{th}$
entry is $1$ and all other entries are zero. We define
$b_{i}=(1,e_{i},a_{i})\in\mathbb{Z}^{m+n+1}$ for $i\in[1,m]$ and
$b=(k,1^{m},a)\in\mathbb{Z}^{m+n+1}$. We then add all filling vectors
$(0,0^{i},1^{j},0^{l},0^{n})$, where $i+j+l=m$. Consider the set
$B=\\{b_{1},\ldots,b_{m}\\}\cup F$, where $F$ is the set of all filling
vectors.

We claim that there is a subset $S\subseteq A$ of size $k$ with $\sum_{x\in
S}x=a$ if and only if $b\in B^{\leq 2k+1}$.333Note that when writing $b\in
B^{\leq 2k+1}$ we use the multiplicative notation for the abelian group
$\mathbb{Z}^{m+n+1}$. First assume that $\sum_{x\in S}x=a$ with $|S|=k$. Let
$S=\\{a_{i_{1}},\ldots,a_{i_{k}}\\}$ with $i_{1}<i_{2}<\cdots<i_{k}$. Then
$\sum_{j=1}^{k}b_{i_{j}}=(k,v,a)$, where $v\in\\{0,1\\}^{m}$ has exactly $k$
ones. Hence, by adding at most $k+1$ filling vectors to
$\sum_{j=1}^{k}b_{i_{j}}$, we obtain $b=(k,1^{m},a)$.

For the other direction, assume that $b\in B^{\leq 2k+1}$ and let
$b=\sum_{i=1}^{l}c_{i}$ with $c_{i}\in B$ and $l\leq 2k+1$. Inspecting the
first coordinate shows that the sum $\sum_{i=1}^{l}c_{i}$ contains exactly $k$
vectors from $\\{b_{1},\ldots,b_{m}\\}$. Moreover, since the entries at
positions $2,\ldots,m+1$ in $b$ are $1$, these $k$ vectors must be pairwise
different. By projecting onto the last coordinate we obtain a subset
$S\subseteq A$ of size $k$ with $\sum_{x\in S}x=a$.

The above idea also works for
$\mathsf{C}\in\\{\mathsf{CycPG},\mathsf{AbPG},\mathsf{FAbG},\mathbb{Z},\mathbb{N},\mathbb{N}^{*}\\}$.
For $\mathsf{C}=\mathbb{Z}$ (and similarly $\mathsf{C}=\mathbb{N}$) we can use
the above reduction together with
$\mathsf{pKS}_{\leq}[\mathbb{Z}^{*}]\leq^{\mathsf{fpt}}\mathsf{pKS}_{\leq}[\mathbb{Z}]$,
which is obtained as follows:

$\displaystyle\mathsf{pKS}_{\leq}[\mathbb{Z}^{*}]\quad$
$\displaystyle\leq^{\mathsf{fpt}}\quad\mathsf{pKS}[\mathbb{Z}^{*}]$ (Lemma 4)
$\displaystyle\leq^{\mathsf{fpt}}\quad\mathsf{pKS}[\mathbb{N}^{*}]$ (Lemma 2)
$\displaystyle\leq^{\mathsf{fpt}}\quad\mathsf{pKS}[\mathbb{N}]$ (Lemma 3)
$\displaystyle\leq^{\mathsf{fpt}}\quad\mathsf{pKS}_{\leq}[\mathbb{N}]$ (Lemma
5) $\displaystyle\leq^{\mathsf{fpt}}\quad\mathsf{pKS}_{\leq}[\mathbb{Z}].$

Finally, for $\mathsf{C}=\mathsf{FCycG}$ we obtain
$\mathsf{pSSS}[\mathsf{FCycG}]\equiv^{\mathsf{fpt}}\mathsf{pSSS}[\mathsf{CycPG}]\leq^{\mathsf{fpt}}\mathsf{pKS}_{\leq}[\mathsf{CycPG}]\leq^{\mathsf{fpt}}\mathsf{pKS}_{\leq}[\mathsf{FCycG}]$
with Corollary 3 and Lemma 7. ∎

We finally obtain Theorem 4.4 from Theorem 0.F.2. The statements concerning
$\mathsf{W}[1]$ and $\mathsf{W}[3]$ from Theorem 4.4 follow from [4] (where
$\mathsf{W}[1]$-hardness of $\mathsf{pSSS}[\mathbb{Z}]$ was shown) and [1]
(where membership of $\mathsf{pSSS}^{\neq}[\mathbb{Z}]$ in $\mathsf{W}[3]$ was
shown).

##  Appendix 0.G Additional material on cyclic permutation groups

###### Lemma 10

There is an algorithm that given two permutations $\alpha,\beta\in S_{n}$
checks in polynomial time whether $\langle\alpha,\beta\rangle$ is cyclic and
if so returns a permutation $\sigma$ such that
$\langle\alpha,\beta\rangle=\langle\sigma\rangle$ and
$\operatorname{lcm}(\operatorname{ord}(\alpha),\operatorname{ord}(\beta))=\operatorname{ord}(\sigma)$.

###### Proof

On input $\alpha,\beta\in S_{n}$, the algorithm computes the following data:

  1. 1.

$\operatorname{ord}(\alpha)$ and $\operatorname{ord}(\beta)$,

  2. 2.

the prime factorizations $\operatorname{ord}(\alpha)=p_{1}^{a_{1}}\cdots
p_{m}^{a_{m}}$ and $\operatorname{ord}(\beta)=p_{1}^{b_{1}}\cdots
p_{m}^{b_{m}}$ (we assume here that $a_{i}$ or $b_{i}$ is non-zero for every
$i\in[1,m]$),

  3. 3.

the numbers $r=\prod_{i=1}^{m}p_{i}^{x_{i}}$ and
$s=\prod_{i=1}^{m}p_{i}^{y_{i}}$, where for all $i\in[1,m]$ we have

$x_{i}=\begin{cases}0&\text{if }a_{i}\geq b_{i}\\\ a_{i}&\text{if
}a_{i}<b_{i}\end{cases}\text{ and }y_{i}=\begin{cases}0&\text{if
}b_{i}>a_{i}\\\ b_{i}&\text{if }b_{i}\leq a_{i}\end{cases}$

  4. 4.

the permutations $\alpha^{\prime}=\alpha^{r}$, $\beta^{\prime}=\beta^{s}$, and
$\gamma=\alpha^{\prime}\beta^{\prime}$.

If $\langle\alpha,\beta\rangle=\langle\gamma\rangle$ then the algorithm
returns $\gamma$, otherwise it returns “not cyclic”.

We first show that the algorithm is correct, then we argue that it runs in
polynomial time. Clearly, if $\langle\alpha,\beta\rangle$ is not cyclic then
the algorithm will return “not cyclic”. Vice versa suppose there is a
permutation $\sigma$ such that
$\langle\alpha,\beta\rangle=\langle\sigma\rangle$. Then we have
$\operatorname{ord}(\sigma)=|\langle\alpha,\beta\rangle|=\operatorname{lcm}(\operatorname{ord}(\alpha),\operatorname{ord}(\beta))$,
where $\operatorname{lcm}$ denotes the least common multiple. Now let
$\alpha^{\prime}$, $\beta^{\prime}$ and $\gamma$ be as defined in the
algorithm. Then
$\operatorname{ord}(\alpha^{\prime})=\operatorname{ord}(\alpha)/r$ and
$\operatorname{ord}(\beta^{\prime})=\operatorname{ord}(\beta)/s$ and these
numbers are coprime. We obtain
$\operatorname{ord}(\gamma)=\operatorname{ord}(\alpha^{\prime})\operatorname{ord}(\beta^{\prime})=\operatorname{lcm}(\operatorname{ord}(\alpha),\operatorname{ord}(\beta))=\operatorname{ord}(\sigma)$.
Moreover $\gamma\in\langle\alpha,\beta\rangle=\langle\sigma\rangle$. By this
it follows that $\gamma$ is also a generator of $\langle\sigma\rangle$, i.e.,
$\langle\gamma\rangle=\langle\alpha,\beta\rangle$. Hence, checking
$\langle\alpha,\beta\rangle=\langle\gamma\rangle$ succeeds and the algorithm
correctly returns $\gamma$.

We now argue that the algorithm runs in polynomial time. Recall that $n$ (the
degree of the permutations) is given in unary notation. To compute the order
of a permutation we simply have to compute the length of the disjoint cycles
and compute the least common multiple of the lengths which can be computed in
polynomial time. By Lagrange’s theorem both $\operatorname{ord}(\alpha)$ and
$\operatorname{ord}(\beta)$ divide $n!$ and thus $p_{i}\leq n$ for
$i\in[1,m]$. Moreover $m\leq n$ because every prime $p_{i}$ is bounded by $n$.
Furthermore the exponents $a_{i}$ and $b_{i}$ are bounded by $O(\log n)$
because every cycle has length at most $n$. Hence the prime factorizations of
$\operatorname{ord}(\alpha)$ and $\operatorname{ord}(\beta)$ can be computed
in polynomial time. Clearly $\alpha^{\prime},\beta^{\prime}$ and $\gamma$ can
be computed in polynomial time. Finally, in order to check
$\langle\alpha,\beta\rangle=\langle\gamma\rangle$, it suffices to check
whether $\alpha\in\langle\gamma\rangle$ and $\beta\in\langle\gamma\rangle$.
This can be done in polynomial time by [9]. ∎

###### Lemma 11

There is an algorithm that given a list of permutations
$\pi_{1},\ldots,\pi_{m}\in S_{n}$ checks in polynomial time whether
$\langle\pi_{1},\ldots,\pi_{m}\rangle$ is cyclic and if so returns a
permutation $\sigma$ such that
$\langle\pi_{1},\ldots,\pi_{m}\rangle=\langle\sigma\rangle$.

###### Proof

If $\langle\pi_{1},\ldots,\pi_{m}\rangle$ is cyclic then also
$\langle\pi_{1},\ldots,\pi_{l}\rangle$ is cyclic for every $l\leq m$.
Therefore, using Lemma 10 we can first check whether
$\langle\pi_{1},\pi_{2}\rangle$ is cyclic. If this is not the case, then
$\langle\pi_{1},\ldots,\pi_{m}\rangle$ is not cyclic. Otherwise, Lemma 10
returns a permutation $\pi_{1,2}$ such that
$\langle\pi_{1},\pi_{2}\rangle=\langle\pi_{1,2}\rangle$. We then recursively
check whether $\langle\pi_{1,2},\pi_{3},\ldots,\pi_{m}\rangle$ is cyclic. ∎

##  Appendix 0.H Proof of Theorem 4.5

It suffices to show $\mathsf{pSSS}[\mathsf{FAbG}]\in\mathsf{W}[5]$ because by
Lemma 1 we have
$\mathsf{pKS}[\mathsf{FAbG}]\leq^{\mathsf{fpt}}\mathsf{pSSS}[\mathsf{FAbG}]$.
Let $t_{i}=(t_{i,1},\dots,t_{i,d})\in\prod_{j=1}^{d}\mathbb{Z}_{n_{j}}$ for
$i\in[1,m]$, $u=(u_{1},\dots,u_{d})\in\prod_{j=1}^{d}\mathbb{Z}_{n_{j}}$ and
$k\in\mathbb{N}$ be the input for $\mathsf{pSSS}[\mathsf{FAbG}]$. We can
assume that $t_{i,j},u_{j}\in[0,n_{j}-1]$ for all $i\in[1,m]$, $j\in[1,d]$.

First we give a reduction to an equivalent problem, where we avoid
computations modulo $n_{j}$. We have

$\exists x_{1},\ldots,x_{m}\in\\{0,1\\}:\sum_{i=1}^{m}x_{i}=k\text{ and
}\forall j\in[1,d]:\sum_{i=1}^{m}x_{i}t_{i,j}\equiv u_{j}\bmod n_{j}$

if and only if

$\exists x_{1},\ldots,x_{m}\in\\{0,1\\}:\sum_{i=1}^{m}x_{i}=k\text{ and
}\forall j\in[1,d]\;\exists
y\in[0,k-1]:\sum_{i=1}^{m}x_{i}t_{i,j}=u_{j}+y\cdot n_{j}.$

The values $u_{y,j}:=u_{j}+y\cdot n_{j}\in\mathbb{N}$ for $j\in[1,d]$ and
$y\in[0,k-1]$ can be precomputed in $\mathsf{FPT}$. Now the input for our new
problem consists of the tuples $t_{1},\dots,t_{m}$ as defined above, the
parameter $k\in\mathbb{N}$, and a matrix

$\begin{bmatrix}u_{0,1}&\dots&u_{0,d}\\\ \vdots&\ddots&\vdots\\\
u_{k-1,1}&\dots&u_{k-1,d-1}\end{bmatrix}\in\mathbb{N}^{k\times d}$

This representation allows us to do all computations in $\mathbb{N}$.

Now we present an algorithm for the above problem. Most parts of the algorithm
are identical to the $\mathsf{W}[3]$-algorithm of [1] for
$\mathsf{pSSS}^{\neq}[\mathbb{Z}]$. It is straightforward to transform this
algorithm into a $\Sigma_{5,2}$-formula that only depends on $k$. As in [1] we
also represent all numbers in base $r$ with $r=2^{\lceil\log
k\rceil}\in\Theta(k)$ by taking blocks of $\lceil\log k\rceil$ bits in the
binary representations of the numbers. Let us write

$(b_{0},b_{1},\ldots,b_{p})_{r}=\sum_{i=0}^{p}b_{i}r^{i}$

for $b_{0},\ldots,b_{p}\in[0,r-1]$. Let $t_{i,j,p}$ (resp., $u_{y,j,p}$) be
the $p^{th}$ base-$r$ digit of the number $t_{i,j}$ (resp., $u_{y,j}$). We
start with $p=0$. Assume that $m_{j}+1$ is the maximal number of digits in the
base-$r$ expansions of the numbers $t_{i,j}$ for $i\in[1,m]$.

  1. 1.

Existentially guess $k$ elements $t_{i_{1}},\ldots,t_{i_{k}}$
($i_{1}<i_{2}<\cdots<i_{k}$).

  2. 2.

Universally guess a coordinate $j\in[1,d]$.

  3. 3.

Existentially guess a $y\in[0,k-1]$. The remaining goal is to check whether
$u_{y,j}=t_{i_{1},j}+\cdots+t_{i_{k},j}$. We define the following base-$r$
digits, where $p\in[0,m_{j}]$:

$\displaystyle s_{p}$ $\displaystyle=$
$\displaystyle(t_{i_{1},j,p}+\cdots+t_{i_{k},j,p})\bmod r\in[0,r-1],$
$\displaystyle s_{m_{j}+1}$ $\displaystyle=$ $\displaystyle 0,$ $\displaystyle
c_{0}$ $\displaystyle=$ $\displaystyle 0,$ $\displaystyle c_{p+1}$
$\displaystyle=$
$\displaystyle(t_{i_{1},j,p}+\cdots+t_{i_{k},j,p})\;\mathrm{div}\;r\in[0,r-1].$

Note that $t_{i_{1},j,p}+\cdots+t_{i_{k},j,p}\leq r(r-1)=r^{2}-r$ and

$t_{i_{1}}+\cdots+t_{i_{k}}=\sum_{p=0}^{m_{j}+1}(s_{p}r^{p}+c_{p}r^{p})=\underbrace{(s_{0},\ldots,s_{m_{j}+1})_{r}}_{v}+\underbrace{(c_{0},\ldots,c_{m_{j}+1})_{r}}_{w}.$

The new goal is to check whether $v+w=u_{y,j}$. Note that when adding $v$ and
$w$, the maximal carry that can arrive at a certain position is $1$ (since
$2(r-1)+1=(r-1,1)_{r}$).

  4. 4.

Universally select a position $p\in[0,m_{j}+1]$.

  5. 5.

Compute $\delta=(u_{y,j,p}-s_{p}-c_{p})\bmod r$. Reject if $\delta$ is neither
$0$ nor $1$.

  6. 6.

If $\delta=0$ then do the following (we verify that no carry arrives at
position $p$):

    1. (a)

Universally select a position $p^{\prime}\in[0,p-1]$ that generates a carry
(i.e., $s_{p^{\prime}}+c_{p^{\prime}}\geq r$).

    2. (b)

Existentially select a position $q\in[p^{\prime}+1,p-1]$ such that a carry
from position $q-1$ is not propagated through position $q$ (i.e.,
$s_{q}+c_{q}<r-1$).

  7. 7.

If $\delta=1$ then do the following (we verify that a carry arrives at
position $p$):

    1. (a)

Universally select a position $p^{\prime}\in[-1,p-1]$.

    2. (b)

If $p^{\prime}=-1$ or the digits at position $p^{\prime}$ do not propagate a
carry (i.e., $s_{p^{\prime}}+c_{p^{\prime}}<r-1$) then existentially select a
position $q\in[p^{\prime}+1,p-1]$ such that a carry is generated at position
$q$ (i.e., $s_{q}+c_{q}\geq r$).

It is straightforward (but tedious) to translate the above algorithm into a
$\Sigma_{5,2}$-sentence that only depends on the parameter $k$. The
existential (resp., universal) guesses correspond to existential (resp.,
universal) quantifiers in the formula. The constructed formula is model-
checked in a structure that is constructed from the input numbers. We just
sketch this structure. For each of the following elements we add an element to
the universe of the structure:

  1. (1)

every $i\in[1,m]$, where $i$ represents the tuple $t_{i}$,

  2. (2)

every dimension $j\in[1,d]$,

  3. (3)

every $y\in[0,k-1]$,

  4. (4)

every position $p$ that exists in one of the base-$r$ expansions of the
numbers $t_{i,j}$ and $u_{y,j}$, and

  5. (5)

all $\alpha\in[0,r-1]$ that stand for the base-$r$ digits.

Moreover, we need the following predicates:

  * •

a separate unary predicate for the numbers from (1)–(4) in order to be able to
quantify over these elements,

  * •

a 4-ary relation that contains the tuple $(i,j,p,\alpha)$ if
$\alpha\in[0,r-1]$ is the digit at position $p$ in the number $t_{i,j}$,

  * •

a 4-ary relation that contains the tuple $(y,j,p,\alpha)$ if
$\alpha\in[0,r-1]$ is the digit at position $p$ in the number $u_{y,j}$,

  * •

the natural linear order on the positions from (4), and

  * •

the natural linear order on $[0,r-1]$.

Note that the elements in (1)–(5) do not have to be disjoint. Conditions like
$(u_{y,j,p}-s_{p}-c_{p})\bmod r=0$ can be expressed by quantifier-free
formulas, whose size only depends on $k$. We leave the details to the reader.
∎

##  Appendix 0.I Additional material for Section 5

###  0.I.1 Detailed proof of Theorem 5.2

We prove the theorem in the following order:

  1. (i)

$\mathsf{pKS}_{\leq}[\mathbb{N}]\leq^{\mathsf{fpt}}$ p-unbounded-change-approx

  2. (ii)

p-unbounded-change-approx $\leq^{\mathsf{fpt}}$ p-bounded-change-approx

  3. (iii)

$\mathsf{pSSS}_{\leq}^{\neq}[\mathbb{N}]$ $\leq^{\mathsf{fpt}}$ p-0-1-change-
approx

  4. (iv)

p-0-1-change-approx $\leq^{\mathsf{fpt}}$ p-bounded-change-approx

  5. (v)

p-bounded-change-approx $\leq^{\mathsf{fpt}}$
$\mathsf{pSSS}_{\leq}[\mathbb{Z}]$

Since (iv) is trivial and (iii) can be proven analogously to (i) we only show
the reductions for (i), (ii) and (v). For (i) notice that an instance of
$\mathsf{pKS}_{\leq}[\mathbb{N}]$ can be transformed into an equivalent
instance of p-unbounded-change-approx by taking the linear function
$f(x,y)=(k+1)x+y$.

For (ii) let $c,c_{1},\ldots,c_{m},f(x,y)=ax+by$, and $k$ be the input data
for p-unbounded-change-approx. By setting $b_{i}=k$ for $i\in[1,m]$ we obtain
an equivalent instance of p-bounded-change-approx if $b>0$. If $b=0$ then also
$a=0$ and hence the condition
$f(\sum_{i=1}^{m}x_{i}c_{i}-c,\sum_{i=1}^{m}x_{i})\leq k$ is always satisfied.
The p-unbounded-change-approx-instance is then positive if and only if $c=0$
or $c_{i}>0$ for at least one $i\in[1,m]$.

It remains to show (v). Let $c,c_{1},b_{1},\dots,c_{m},b_{m},f(x,y)=ax+by$,
and $k$ be the input data for p-bounded-change-approx. If $a=0=b$ the instance
is positive if and only if $\sum_{i=1}^{m}b_{i}c_{i}\geq c$.

Suppose now that $a=0$ and $b\geq 1$ and w.l.o.g. $c_{1}>c_{2}>\cdots>c_{m}$.
We show that it can be checked in polynomial time whether the p-bounded-
change-approx-instance is positive. The latter holds if and only if there
exist $x_{i}\in[0,b_{i}]$ $(i\in[1,m])$ with $\sum_{i=1}^{m}x_{i}c_{i}\geq c$
and $\sum_{i=1}^{m}x_{i}\leq\lfloor k/b\rfloor$. We can w.l.o.g. assume that
$b_{i}>0$ for all $i\in[1,m]$. If
$\sum_{i=1}^{m}b_{i}\leq\lfloor\frac{k}{b}\rfloor$ then it suffices to check
whether $\sum_{i=1}^{m}b_{i}c_{i}\geq c$. If
$\sum_{i=1}^{m}b_{i}>\lfloor\frac{k}{b}\rfloor$ then we compute the unique
$l\in[0,m-1]$ and $b^{\prime}_{l+1}<b_{l+1}$ such that
$\sum_{i=1}^{l}b_{i}+b^{\prime}_{l+1}=\left\lfloor\frac{k}{b}\right\rfloor$.
It then suffices to check whether
$\sum_{i=1}^{l}b_{i}c_{i}+b^{\prime}_{l+1}c_{l+1}\geq c$.

The case that remains is $a,b\geq 1$. We define the following integers:

$\displaystyle d$ $\displaystyle=c\cdot 2^{\\#(ka)+\\#(kb)}$ $\displaystyle
d_{i}$ $\displaystyle=b-1+c_{i}\cdot 2^{\\#(ka)+\\#(kb)}\text{ for }i\in[1,m]$
$\displaystyle d_{0}$ $\displaystyle=-1$ $\displaystyle d_{m+1}$
$\displaystyle=(1-a)\cdot 2^{\\#(kb)}-2^{\\#(ka)+\\#(kb)}$ $\displaystyle
d_{m+2}$ $\displaystyle=2^{\\#(kb)}$

Moreover, we set $k=b_{0}=b_{m+1}=b_{m+2}$.

###### Claim 4

The p-bounded-change-approx-instance
$c,c_{1},b_{1},\dots,c_{m},b_{m},f(x,y)=ax+by$, $k$ is positive iff there
exist $x_{i}\in[0,b_{i}]$ $(0\leq i\leq m+2)$ such that

$\sum_{i=0}^{m+2}x_{i}d_{i}=d\quad\text{ and }\quad\sum_{i=0}^{m+2}x_{i}\leq
k.$

First suppose the p-bounded-change-approx-instance is positive. Then there
exist $x_{i}\in[0,b_{i}]$ with

$\sum_{i=1}^{m}x_{i}c_{i}\geq c\quad\text{ and }\quad
a\bigg{(}\sum_{i=1}^{m}x_{i}c_{i}-c\bigg{)}+b\sum_{i=1}^{m}x_{i}\leq k.$

By choosing $x_{0}=(b-1)\sum_{i=1}^{m}x_{i}$ and
$x_{m+1}=\sum_{i=1}^{m}x_{i}c_{i}-c$ and
$x_{m+2}=(a-1)(\sum_{i=1}^{m}x_{i}c_{i}-c)$ we obtain

$\displaystyle\sum_{i=0}^{m+2}x_{i}d_{i}=\phantom{}$
$\displaystyle(b-1)\big{(}\sum_{i=1}^{m}x_{i}\big{)}d_{0}+\sum_{i=1}^{m}x_{i}d_{i}+\big{(}\sum_{i=1}^{m}x_{i}c_{i}-c\big{)}d_{m+1}+(a-1)\big{(}\sum_{i=1}^{m}x_{i}c_{i}-c\big{)}d_{m+2}$
$\displaystyle=\phantom{}$
$\displaystyle-(b-1)\sum_{i=1}^{m}x_{i}+\sum_{i=1}^{m}x_{i}(b-1)+\sum_{i=1}^{m}x_{i}c_{i}\cdot
2^{\\#(ka)+\\#(kb)}$
$\displaystyle+\big{(}\sum_{i=1}^{m}x_{i}c_{i}-c\big{)}(1-a)\cdot
2^{\\#(kb)}-\big{(}\sum_{i=1}^{m}x_{i}c_{i}-c\big{)}\cdot 2^{\\#(ka)+\\#(kb)}$
$\displaystyle+(a-1)\big{(}\sum_{i=1}^{m}x_{i}c_{i}-c\big{)}\cdot 2^{\\#(kb)}$
$\displaystyle=\phantom{}$ $\displaystyle\sum_{i=1}^{m}x_{i}c_{i}\cdot
2^{\\#(ka)+\\#(kb)}-\big{(}\sum_{i=1}^{m}x_{i}c_{i}-c\big{)}\cdot
2^{\\#(ka)+\\#(kb)}$ $\displaystyle=\phantom{}$ $\displaystyle c\cdot
2^{\\#(ka)+\\#(kb)}=d$

and

$\displaystyle\sum_{i=0}^{m+2}x_{i}$
$\displaystyle=(b-1)\sum_{i=1}^{m}x_{i}+\sum_{i=1}^{m}x_{i}+\sum_{i=1}^{m}x_{i}c_{i}-c+(a-1)\big{(}\sum_{i=1}^{m}x_{i}c_{i}-c\big{)}$
$\displaystyle=a\big{(}\sum_{i=1}^{m}x_{i}c_{i}-c\big{)}+b\sum_{i=1}^{m}x_{i}\leq
k$

Therefore we have $x_{0},x_{m+1},x_{m+2}\in[0,k]$. Thus $x_{i}\in[0,b_{i}]$
for all $i\in[0,m+2]$.

For the other direction in Claim 4 assume that $x_{i}\in[0,b_{i}]$ are such
that

$\sum_{i=0}^{m+2}x_{i}d_{i}=d\quad\text{ and }\quad\sum_{i=0}^{m+2}x_{i}\leq
k.$ (19)

We bring the left equation in (19) in a form where all numbers are positive:

$\sum_{i=1}^{m}x_{i}d_{i}+x_{m+2}d_{m+2}=d+x_{0}(-d_{0})+x_{m+1}(-d_{m+1}),$

or, after plugging in the values of the $d_{i}$ and rearranging,

$\displaystyle\sum_{i=1}^{m}x_{i}(b-1)$ $\displaystyle\ +\ $ $\displaystyle
x_{m+2}$ $\displaystyle\ 2^{\\#(kb)}$ $\displaystyle\ +\
\bigg{(}\sum_{i=1}^{m}x_{i}c_{i}\bigg{)}$ $\displaystyle\ 2^{\\#(ka)+\\#(kb)}$
$\displaystyle=$ $\displaystyle x_{0}$ $\displaystyle\ +\ $ $\displaystyle
x_{m+1}(a-1)$ $\displaystyle\ 2^{\\#(kb)}$ $\displaystyle\ +\ (c+x_{m+1})$
$\displaystyle\ 2^{\\#(ka)+\\#(kb)}$

Note that $\sum_{i=1}^{m}x_{i}(b-1)$ and $x_{0}$ are bounded by $kb$ and
therefore have at most $\\#(kb)$ bits. All other terms in the above equation
are multiplied with $2^{\\#(kb)}$ and therefore do not affect the first
$\\#(kb)$ bits. Similarly, $x_{m+2}$ and $x_{m+1}(a-1)$ are bounded by $ka$
and therefore have at most $\\#(ka)$ bits. We therefore split the above
equation into three simultaneous equations:

$\displaystyle\sum_{i=1}^{m}x_{i}(b-1)$ $\displaystyle=$ $\displaystyle x_{0}$
(20) $\displaystyle x_{m+2}$ $\displaystyle=$ $\displaystyle x_{m+1}(a-1)$
(21) $\displaystyle\sum_{i=1}^{m}x_{i}c_{i}$ $\displaystyle=$ $\displaystyle
c+x_{m+1}$ (22)

By (22) we have $x_{m+1}=\sum_{i=1}^{m}x_{i}c_{i}-c$. Together with (21) this
gives us $x_{m+2}=(a-1)(\sum_{i=1}^{m}x_{i}c_{i}-c)$. Adding up all variables
and using (20) yields

$\displaystyle k\geq\sum_{i=0}^{m+2}x_{i}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{m}x_{i}(b-1)+\sum_{i=1}^{m}x_{i}+\sum_{i=1}^{m}x_{i}c_{i}-c+(a-1)\bigg{(}\sum_{i=1}^{m}x_{i}c_{i}-c\bigg{)}$
$\displaystyle=$ $\displaystyle
a\bigg{(}\sum_{i=1}^{m}x_{i}c_{i}-c\bigg{)}+b\sum_{i=1}^{m}x_{i}.$

Moreover since we have $x_{m+1}\geq 0$, (22) finally implies
$\sum_{i=1}^{m}x_{i}c_{i}\geq c$ which proves the claim. ∎

By Claim 4 we obtain an equivalent instance of
$\mathsf{pSSS}_{\leq}[\mathbb{Z}]$ by defining a list where for $i\in[0,m+2]$
the number $d_{i}$ is contained exactly $b_{i}$ times. ∎

###  0.I.2 NP-hardness of the approximative change-making problems for $a\geq
1$ and $b=0$

###### Theorem 0.I.1

Let $a\geq 1$ and $b=0$. Then for all $d\geq 1$ the $d^{th}$ slices of the
problems p-unbounded-change-approx, p-bounded-change-approx and p-0-1-change-
approx are NP-complete. Moreover, these three problems are in para-NP.

###### Proof

Membership of all three problems in NP is straightforward. We guess numbers
$x_{i}\in[0,\lceil\frac{c}{c_{i}}\rceil]$ (for p-unbounded-change-approx),
$x_{i}\in[0,b_{i}]$ (for p-bounded-change-approx) and $x_{i}\in\\{0,1\\}$ (for
p-0-1-change-approx), respectively, and verify

$\sum_{i=1}^{m}x_{i}c_{i}\geq c\quad\text{ and }\quad
a\left(\sum_{i=1}^{m}x_{i}c_{i}-c\right)\leq d.$

The same algorithm shows membership in paraNP for the parameterized problems.

Now we show NP-hardness. The proof uses a modification of the construction
given in the appendix of [10]. We start with an instance of the NP-complete
problem subset sum where we are given positive integers $a_{1}\leq
a_{2}\leq\cdots\leq a_{m}$ and $a\in\mathbb{N}$ in binary encoding. The
question is whether there exist $x_{1},\ldots,x_{m}\in\\{0,1\\}$ such that
$\sum_{i=1}^{m}x_{i}a_{i}=a$. W.l.o.g. we can assume $a\leq
ma_{m}<2^{\\#(ma_{m})}$. Otherwise the instance is negative and the reduction
yields a fixed negative instance. Furthermore we can assume w.l.o.g.
$a_{i}\neq 0$. If $a>0$ we can remove from the list all numbers that are equal
to $0$. In the case $a=0$ the instance is trivially positive by choosing
$x_{i}=0$ for all variables and the reduction yields a fixed positive
instance. We define for $i\in[1,m]$ the numbers

$\displaystyle c_{2i-1}$ $\displaystyle=$ $\displaystyle
0+2^{\\#(ma_{m})+(i-1)\\#(m)}+2^{\\#(ma_{m})+m\\#(m)},$ $\displaystyle c_{2i}$
$\displaystyle=$ $\displaystyle
a_{i}+2^{\\#(ma_{m})+(i-1)\\#(m)}+2^{\\#(ma_{m})+m\\#(m)},\text{ and }$
$\displaystyle c$ $\displaystyle=$ $\displaystyle
a+\sum_{i=1}^{m}2^{\\#(ma_{m})+(i-1)\\#(m)}+m\cdot 2^{\\#(ma_{m})+m\\#(m)}.$

Note that we have $c_{1}<c_{2}<\dots<c_{2m}$.

###### Claim 5

If $\sum_{i=1}^{m}x_{i}a_{i}=a$ with $x_{i}\in\\{0,1\\}$ then we have

$\sum_{i=1}^{m}(x_{i}c_{2i}+(1-x_{i})c_{2i-1})=c.$

We have

$\displaystyle\sum_{i=1}^{m}(x_{i}c_{2i}+(1-x_{i})c_{2i-1})$
$\displaystyle=\sum_{i=1}^{m}x_{i}a_{i}+\sum_{i=1}^{m}2^{\\#(ma_{m})+(i-1)\\#(m)}+\sum_{i=1}^{m}2^{\\#(ma_{m})+m\\#(m)}$
$\displaystyle=a+\sum_{i=1}^{m}2^{\\#(ma_{m})+(i-1)\\#(m)}+m\cdot
2^{\\#(ma_{m})+m\\#(m)}$ $\displaystyle=c,$

which proves the claim. ∎

###### Claim 6

Assume that $\sum_{i=1}^{2m}x_{i}c_{i}=c$ for
$x_{1},\ldots,x_{2m}\in\mathbb{N}$. Then the following holds:

  1. 1.

$\sum_{i=1}^{2m}x_{i}\leq m$

  2. 2.

For $i\in[1,m]$ we have $x_{2i-1},x_{2i}\in\\{0,1\\}$ and $x_{2i-1}=1$ if and
only if $x_{2i}=0$.

  3. 3.

$\sum_{i=1}^{m}x_{2i}a_{i}=a$

For the first statement, suppose that $\sum_{i=1}^{2m}x_{i}>m$. Then we obtain

$\displaystyle\sum_{i=1}^{2m}x_{i}c_{i}$ $\displaystyle\geq$
$\displaystyle(m+1)\cdot c_{1}$ $\displaystyle=$
$\displaystyle(m+1)\cdot(2^{\\#(ma_{m})}+2^{\\#(ma_{m})+m\\#(m)})$
$\displaystyle\geq$ $\displaystyle 2^{\\#(ma_{m})}+(m+1)\cdot
2^{\\#(ma_{m})+m\\#(m)}$ $\displaystyle>$ $\displaystyle a+(m+1)\cdot
2^{\\#(ma_{m})+m\\#(m)}$ $\displaystyle=$ $\displaystyle a+m\cdot
2^{\\#(ma_{m})+m\\#(m)}+2^{\\#(ma_{m})}\cdot 2^{m\\#(m)}$ $\displaystyle>$
$\displaystyle a+m\cdot
2^{\\#(ma_{m})+m\\#(m)}+2^{\\#(ma_{m})}\cdot\sum_{i=1}^{m}\big{(}2^{\\#(m)}\big{)}^{i-1}$
$\displaystyle=$ $\displaystyle a+m\cdot
2^{\\#(ma_{m})+m\\#(m)}+\sum_{i=1}^{m}2^{\\#(ma_{m})+(i-1)\\#(m)}\ =\ c$

which is a contradiction.

Let us now show the second statement of Claim 6. By the first statement we
have $\sum_{i=1}^{2m}x_{i}\leq m$. Hence, the sum
$c=\sum_{i=1}^{2m}x_{i}c_{i}$ is a sum of $m$ numbers $c_{i}$, possibly with
repetitions. The binary representations of the $c_{i}$ are divided into
blocks. The first block contains the $\\#(ma_{m})$ first bits and the next
blocks consist of exactly $\\#(m)$ bits each. The lengths of the blocks are
such that in the sum $\sum_{i=1}^{2m}x_{i}c_{i}$ a carry cannot enter a block
from the previous block. The bit at position $1+\\#(ma_{m})+(i-1)\\#(m)$
(i.e., the first bit of the $i^{th}$ block) in $c,c_{2i-1},c_{2i}$ is $1$ (due
to the summand $2^{\\#(ma_{m})+(i-1)\\#(m)}$ in these numbers). In all other
numbers $c_{j}$, the bit at position $1+\\#(ma_{m})+(i-1)\\#(m)$ is zero and
by adding at most $m$ numbers $c_{i}$ one cannot get a carry at position
$1+\\#(ma_{m})+(i-1)\\#(m)$. This implies that $x_{2i-1},x_{2i}\in\\{0,1\\}$
and $x_{2i-1}=1$ if and only if $x_{2i}=0$.

Finally, the third statement of Claim 6 follows from the identity
$c=\sum_{i=1}^{2m}x_{i}c_{i}$ (where $\sum_{i=1}^{2m}x_{i}\leq m$ by the first
statement) and only taking the first block consisting of the $\\#(ma_{m})$
low-order bits. ∎

Claim 6 gives us a reduction from the subset sum equation

$\sum_{i=1}^{m}x_{i}a_{i}=a$

to an equation

$\sum_{i=1}^{2m}x_{i}c_{i}=c$

with $c_{1}<\dots<c_{2m}$. Moreover since by Claim 6 (second statement) it is
ensured that we have for all variables $x_{i}\in\\{0,1\\}$ this reduction
works in both the bounded and unbounded setting.

Now we come to the actual reduction from subset sum to the $d^{th}$ slice of
p-unbounded-change-approx (resp., p-0-1-change-approx). We have
$\sum_{i=1}^{2m}x_{i}c_{i}=c$ if and only if
$\sum_{i=1}^{2m}x_{i}(d+1)c_{i}=(d+1)c$, which holds if and only if the
following two conditions hold

$\sum_{i=1}^{2m}x_{i}(d+1)c_{i}\geq(d+1)c$

and

$a\left(\sum_{i=1}^{m}x_{i}(d+1)c_{i}-(d+1)c\right)\leq d$

Note that $a\geq 1$. This concludes the reduction. ∎