# Fixed Points and Attractors of Reactantless and Inhibitorless Reaction
Systems

Rocco Ascone†111Corresponding author Giulia Bernardini† Luca
Manzoni222University of Trieste, Italy

###### Abstract

Reaction systems are discrete dynamical systems that model biochemical
processes in living cells using finite sets of reactants, inhibitors, and
products. We investigate the computational complexity of a comprehensive set
of problems related to the existence of fixed points and attractors in two
constrained classes of reaction systems, in which either reactants or
inhibitors are disallowed. These problems have biological relevance and have
been extensively studied in the unconstrained case; however, they remain
unexplored in the context of reactantless or inhibitorless systems.
Interestingly, we demonstrate that although the absence of reactants or
inhibitors simplifies the system’s dynamics, it does not always lead to a
reduction in the complexity of the considered problems.

##  1 Introduction

Reaction systems are an abstract model of computation inspired by the chemical
reactions in living cells, introduced by Ehrenfeucht and Rozenberg almost two
decades ago [1, 2]. The idea at the basis of reaction systems is that the
processes carried out by biochemical reactions within a cell can be described
through a finite set of entities, modelling different substances, and a finite
set of rules, modelling reactions. A reaction is defined by a set of
reactants, a set of inhibitors and a set of products: if any current set of
entities (defining a _state_ of the reaction system) includes the set of
reactants and does not contain any of the inhibitors, the reaction takes place
and the products are generated.

Reaction systems are a _qualitative model_ : they assume that if a reactant is
present at a certain state, then its amount is always enough for all the
reactions that use it to take place (i.e., reactions do not conflict even if
they share some resources). The next state of the reaction system is then
given by the union of the products of the reactions that took place.

Despite the simplicity of this formulation, it has been proven that reaction
systems can simulate a variety of real-world biological processes [3],
including heat shock response [4], gene regulatory networks [5] and oncogenic
signalling [6]. Studying the computational complexity of the dynamics of
reaction systems is also a rich and active research area [7, 8, 9, 10, 11];
while the standard model for reaction systems does not pose any constraints on
the number of reactants and inhibitors involved in the reactions, a different
line of research is focused on the study of reaction systems with limited
resources (i.e., bounding the number of reactants and/or inhibitors involved
in any reaction) [12, 13, 14].

This work is in the latter vein and studies the computational complexity of
deciding on the occurrence of behaviors related to fixed points, attractors
and result functions in the special classes of _reactantless_ and
_inhibitorless_ reaction systems. Since reaction systems can be used to model
biological processes, these questions have biological relevance: for instance,
determining whether fixed points and cycles are present is crucial in
modelling gene regulatory networks [15, 16]; and attractors can represent
cellular types or states [17].

To the best of our knowledge, the only existing works studying the complexity
of dynamical behaviors in reactantless and inhibitorless reaction systems are
concerned with the reachability problem [13] and the evolvability problem [18]
(the latter work considering a different type of reaction systems, recently
introduced by Ehrenfeucht et al. [19]). This work is thus an important step
towards a full understanding of the dynamics in these constrained models.

Problem | $\mathcal{RS}(\infty,\infty)$ | $\mathcal{RS}(0,\infty)$ | $\mathcal{RS}(\infty,0)$
---|---|---|---
A given state is a fixed point attractor |  NP-c [20] | NP-c (Thm. 7) | NP-c (Thm. 5)
$\exists$ fixed point |  NP-c [20] | NP-c (Thm. 8) |  P [21]
$\exists$ common fixed point |  NP-c [20] | NP-c (Cor. 9) | NP-c (Thm. 22)
sharing all fixed points |  coNP-c [20] | coNP-c (Thm. 19) | coNP-c (Thm. 24)
$\exists$ fixed point attractor |  NP-c [20] | NP-c (Thm. 10) | Unknown
$\exists$ common fixed point attractor |  NP-c [20] | NP-c (Cor. 11) | NP-c (Cor. 23)
sharing all fixed points attractors |  $\mathbf{\Pi}_{2}^{\textnormal{{P}}}$-c [20] |  $\mathbf{\Pi}_{2}^{\textnormal{{P}}}$-c (Cor. 18) |  $\mathbf{\Pi}_{2}^{\textnormal{{P}}}$-c (Thm. 26)
$\exists$ fixed point not attractor |  $\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$-c (Cor. 16) |  $\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$-c (Thm. 12) |  $\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$-c (Cor. 27)
$\exists$ common fixed point not attractor |  $\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$-c (Cor. 17) |  $\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$-c (Cor. 15) |  $\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$-c (Cor. 28)
sharing all fixed points not attractors | coNP-c (Cor. 21) | coNP-c (Cor. 20) | coNP-c (Cor. 25)
$\mathrm{res}_{\mathcal{A}}=\mathrm{res}_{\mathcal{B}}$ | coNP-c (Thm. 29) | P (Cor. 34) | P (Cor. 32)
res bijective |  coNP-c [22] | P (Cor. 41) | P (Cor. 40)

Table 1: Computational complexity of the problems studied in this work for
different classes of reaction systems. NP-c, coNP-c,
$\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$-c and
$\mathbf{\Pi}_{2}^{\textnormal{{P}}}$-c are shorthands for NP-complete, coNP-
complete, $\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$-complete and
$\mathbf{\Pi}_{2}^{\textnormal{{P}}}$-complete, respectively;
$\mathcal{RS}(\infty,\infty)$, $\mathcal{RS}(0,\infty)$ and
$\mathcal{RS}(\infty,0)$ denote unconstrained, reactantless and inhibitorless
reaction systems, respectively (see Def. 1). Light-blue cells contain the
results proved in this paper.

The main contributions of this study are summarized in Table 1 (light-blue
cells). It is interesting to notice that, although the dynamical behaviors of
the resource-bounded systems are less rich than those of unrestricted systems,
the complexities of the considered problems are not necessarily reduced. For
example, the complexity of deciding whether two reaction systems have a common
fixed point is NP-complete in the general case and it remains so in both the
resource-bounded classes we consider. In contrast, e.g., deciding whether the
result function is bijective is NP-complete in the unconstrained case, while
it can be done in polynomial time in reactantless and inhibitorless systems.

Furthermore, the complexity of a problem in reactantless reaction systems is
not always the same as in inhibitorless systems: e.g., deciding on the
existence of a fixed point can be done in polynomial time in inhibitorless
reaction systems, while it is an NP-complete problem in reactantless systems.
The complexities of different problems for different classes of reaction
systems thus vary in a non-uniform way.

This paper is organized as follows. In Section 2, we provide basic notions on
reaction systems and introduce the notation we use throughout the paper. In
Section 3 we report a description of reaction systems and their dynamics in
terms of logical formulae which will be useful to prove most of our results.
In Section 4, we study the problem of deciding whether a given state is a
fixed point attractor in both constrained models. In Section 5 we study the
complexities of fixed point problems in reactantless systems; in Section 6 we
study the same problems in inhibitorless systems. In Section 7 we study the
problem of deciding whether two reaction systems have the same result function
both in the general model and in the constrained classes. In Section 8 we
consider the problem of deciding whether the result function is bijective both
in reactantless and inhibitorless systems. Finally, in Section 9 we discuss
our results and suggest future research directions.

##  2 Basics Notions

In this section, we introduce the notation used in the paper and the main
definitions concerning reaction systems.

Given a finite set $S$ of _entities_ , a _reaction_ $a$ over $S$ is a triple
$(R_{a},I_{a},P_{a})$ of subsets of $S$333While we do not restrict $R_{a}$ and
$I_{a}$ to be disjoint, as it is usually done, it should be clear that all the
results of the paper hold even then this assumption holds.; the set $R_{a}$ is
the set of _reactants_ , $I_{a}$ is the set of _inhibitors_ , and $P_{a}$ is
the nonempty set of _products_. We remark that in this paper the set of
reactants and inhibitors of a reaction are allowed to be empty as in the
original definition [1]. The set of all reactions over $S$ is denoted by
$\text{rac}(S)$. A _reaction system_ (RS) is a pair $\mathcal{A}=(S,A)$ where
$S$ is a finite set of entities, called the _background set_ , and
$A\subseteq\text{rac}(S)$.

Given a _state_ $T\subseteq S$, a reaction $a$ is said to be _enabled_ in T
when $R_{a}\subseteq T$ and $I_{a}\cap T=\varnothing$. The _result function_
$\mathrm{res}_{a}:2^{S}\to 2^{S}$ of $a$, where $2^{S}$ denotes the power set
of $S$, is defined as

$\mathrm{res}_{a}(T)\coloneqq\begin{cases}P_{a}&\text{if $a$ is enabled by
$T$}\\\ \varnothing&\text{otherwise}.\end{cases}$

The definition of $\mathrm{res}_{a}$ naturally extends to sets of reactions.
Indeed, given $T\subseteq S$ and $A\subseteq\text{rac}(S)$, define
$\mathrm{res}_{A}(T)\coloneqq\bigcup_{a\in A}\mathrm{res}_{a}(T)$. The result
function $\mathrm{res}_{\mathcal{A}}$ of a RS $\mathcal{A}=(S,A)$ is defined
to be equal to $\mathrm{res}_{A}$, i.e., the result function on the whole set
of reactions.

In this way, any RS $\mathcal{A}=(S,A)$ induces a discrete dynamical system
where the state set is $2^{S}$ and the next state function is
$\mathrm{res}_{\mathcal{A}}$.

In this paper, we are interested in the dynamics of RS, i.e., the study of the
successive states of the system under the action of the result function
$\mathrm{res}_{\mathcal{A}}$ starting from some initial set of entities. The
set of reactions of $\mathcal{A}$ enabled in a state $T$ is denoted by
$\textnormal{en}_{\mathcal{A}}(T)$. The _orbit_ or _state sequence_ of a given
state $T$ of a RS $\mathcal{A}$ is defined as the sequence of states obtained
by subsequent iterations of $\mathrm{res}_{\mathcal{A}}$ starting from $T$,
namely the sequence
$(T,\mathrm{res}_{\mathcal{A}}(T),\mathrm{res}_{\mathcal{A}}^{2}(T),\dots)$.
We remark that since $S$ is finite, for any state $T$ the sequence
$(\mathrm{res}_{\mathcal{A}}^{n}(T))_{n\in\mathbb{N}}$ is ultimately periodic.

Given a RS $\mathcal{A}$ with background set $S$, a _fixed point_ $T\subseteq
S$ is a state such that $\mathrm{res}_{\mathcal{A}}(T)=T$. A _fixed point
attractor_ is a fixed point $T$ for which there exists a state $U\neq T$ such
that $\mathrm{res}_{\mathcal{A}}(U)=T$. A _fixed point not attractor_ is a
fixed point that is not an attractor, i.e., not reachable from any state other
than $T$ itself.

We now recall the classification of reaction systems in terms of the number of
resources employed per reaction [23].

######  Definition 1.

Let $i,r\in\mathbb{N}$. The class $\mathcal{RS}(r,i)$ consists of all RS
having at most $r$ reactants and $i$ inhibitors for reaction. We also define
the (partially) unbounded classes
$\mathcal{RS}(\infty,i)=\bigcup_{r=0}^{\infty}\mathcal{RS}(r,i)$,
$\mathcal{RS}(r,\infty)=\bigcup_{i=0}^{\infty}\mathcal{RS}(r,i)$, and
$\mathcal{RS}(\infty,\infty)=\bigcup_{r=0}^{\infty}\bigcup_{i=0}^{\infty}\mathcal{RS}(r,i)$.

In the following, we will call $\mathcal{RS}(0,\infty)$ the class of
_reactantless_ systems, and $\mathcal{RS}(\infty,0)$ the class of
_inhibitorless_ systems.

######  Definition 2 ([23]).

Let $\mathcal{A}=(S,A)$ and $\mathcal{A}^{\prime}=(S^{\prime},A)$, with
$S\subseteq S^{\prime}$, be two reaction systems, and let $k\in\mathbb{N}$. We
say that $\mathcal{A}^{\prime}$ _$k$ -simulates_ $\mathcal{A}$ if and only if,
for all $T\subseteq S$ and all $n\in\mathbb{N}$, we have

$\mathrm{res}_{\mathcal{A}}^{n}(T)=\mathrm{res}_{\mathcal{A}^{\prime}}(T)^{kn}\cap
S.$

######  Definition 3 ([23]).

Let $X$ and $Y$ be classes of reaction systems, and let $k\in\mathbb{N}$. We
define the binary relation $\preceq_{k}$ as follows: $X\preceq_{k}Y$ if and
only if for all $\mathcal{A}\in X$ there exists a reaction system in Y that
$l$-simulates $\mathcal{A}$ for some $l\leq k$. We say that $X\preceq Y$ if
and only if $X\preceq_{k}Y$ for some $k\in\mathbb{N}$. We write
$X\approx_{k}Y$ if $X\preceq_{k}Y$ and $Y\preceq_{k}X$, and $X\approx Y$ for
$X\preceq Y\land Y\preceq X$. Finally, the notation $X\prec Y$ is shorthand
for $X\preceq Y\land Y\npreceq X$.

The relation $\preceq$ is a preorder and the relation $\approx$ induces
exactly five equivalence classes [23, Theorem 30]:

$\mathcal{RS}(0,0)\prec\mathcal{RS}(1,0)\prec\mathcal{RS}(\infty,0)\prec\mathcal{RS}(0,\infty)\prec\mathcal{RS}(\infty,\infty).$
(1)

We remark that this classification does not include the number of products as
a parameter because RS can always be assumed to be in _singleton product
normal form_ [24]: any reaction $(R,I,\\{p_{1},\dots,p_{m}\\})$ can be
replaced by the set of reactions $(R,I,\\{p_{1}\\}),\dots,(R,I,\\{p_{m}\\})$
since they produce the same result.

The five equivalence classes in (1) have a characterisation in terms of
functions over the Boolean lattice $2^{S}$ [23], see Table 2.

Class of RS | Subclass of $2^{S}\to 2^{S}$
---|---
$\mathcal{RS}(\infty,\infty)$ | all
$\mathcal{RS}(0,\infty)$ | antitone
$\mathcal{RS}(\infty,0)$ | monotone
$\mathcal{RS}(1,0)$ | additive
$\mathcal{RS}(0,0)$ | constant
Table 2: Functions computed by restricted classed of RS.

Recall that a function $f:2^{S}\to 2^{S}$ is _antitone_ if $X\subseteq Y$
implies $f(X)\supseteq f(Y)$, _monotone_ if $X\subseteq Y$ implies
$f(X)\subseteq f(Y)$, _additive_ (or an __upper-semilattice endomorphism) if
$f(X\cup Y)=f(X)\cup f(Y)$ for all $X,Y\in 2^{S}$. We say that the RS
$\mathcal{A}=(S,A)$ computes the function $f:2^{S}\to 2^{S}$ if
$\mathrm{res}_{\mathcal{A}}=f$.

##  3 Logical Description

In this section, we recall a logical description of RS and formulae related to
their dynamics (see [20] for its first introduction). This description is
sufficient for proving membership in many complexity classes. For the
background notions of logic and descriptive complexity, we refer the reader to
the classical book of Neil Immerman [25].

Each of the problems studied in this work can be characterised by a logical
formula. A RS $\mathcal{A}=(S,A)$ with background set
$S\subseteq\\{0,\dots,n-1\\}$ and $|A|\leq n$ can be described by the
vocabulary
$(\mathsf{S},\mathsf{R}_{\mathcal{A}},\mathsf{I}_{\mathcal{A}},\mathsf{P}_{\mathcal{A}})$,
where $\mathsf{S}$ is a unary relation symbol and
$\mathsf{R}_{\mathcal{A}},\mathsf{I}_{\mathcal{A}},\mathsf{P}_{\mathcal{A}}$
are binary relation symbols. The intended meaning of the symbols is the
following: the set of entities is $S=\\{i:\mathsf{S}(i)\\}$ and each reaction
$a_{j}=(R_{j},I_{j},P_{j})\in A$ is described by the sets $R_{j}=\\{i\in
S:\mathsf{R}_{\mathcal{A}}(i,j)\\}$, $I_{j}=\\{i\in
S:\mathsf{I}_{\mathcal{A}}(i,j)\\}$, and $P_{j}=\\{i\in
S:\mathsf{P}_{\mathcal{A}}(i,j)\\}$. We will also need some additional
vocabularies:
$(\mathsf{S},\mathsf{R}_{\mathcal{A}},\mathsf{I}_{\mathcal{A}},\mathsf{P}_{\mathcal{A}},\mathsf{T})$,
where $\mathsf{T}$ is a unary relation representing a subset of $S$,
$(\mathsf{S},\mathsf{R}_{\mathcal{A}},\mathsf{I}_{\mathcal{A}},\mathsf{P}_{\mathcal{A}},\mathsf{T}_{1},\mathsf{T}_{2})$
with two additional unary relations representing sets, and
$(\mathsf{S},\mathsf{R}_{\mathcal{A}},\mathsf{I}_{\mathcal{A}},\mathsf{P}_{\mathcal{A}},\mathsf{R}_{\mathcal{B}},\mathsf{I}_{\mathcal{B}},\mathsf{P}_{\mathcal{B}})$
denoting two RS’s over the same background set.

The following formulae, introduced in [20], describe the basic properties of
$\mathcal{A}$. The first is true if a reaction $a_{j}$ is enabled in $T$:

$\textsc{en}_{\mathcal{A}}(j,\mathsf{T})\equiv\forall
i(\mathsf{S}(i)\Rightarrow(\mathsf{R}_{\mathcal{A}}(i,j)\Rightarrow\mathsf{T}(j))\land(\mathsf{I}_{\mathcal{A}}(i,j)\Rightarrow\neg\mathsf{T}(j)))$

and the following is verified if $\mathrm{res}_{\mathcal{A}}(T_{1})=T_{2}$ for
$T_{1},T_{2}\subseteq S$:

$\textsc{res}_{\mathcal{A}}(\mathsf{T}_{1},\mathsf{T}_{2})\equiv\forall
i(\mathsf{S}(i)\Rightarrow(\mathsf{T}_{2}(i)\Leftrightarrow\exists
j(\textsc{en}_{\mathcal{A}}(j,\mathsf{T}_{1})\land\mathsf{P}_{\mathcal{A}}(i,j))).$

Notice that $\textsc{en}_{\mathcal{A}}$ and $\textsc{res}_{\mathcal{A}}$ are
both first-order ($\mathsf{FO}$) formulae. We define the bounded second-order
quantifiers $(\forall X\subseteq Y)\varphi$ and $(\exists X\subseteq
Y)\varphi$ as a short-hand for $\forall X(\forall i(X(i)\Rightarrow
Y(i))\Rightarrow\varphi)$ and $\exists X(\forall i(X(i)\Rightarrow
Y(i))\land\varphi)$. We will use the following formulae (given in [20]) to
describe our problems:

$\displaystyle\textsc{fix}_{\mathcal{A}}(\mathsf{T})$
$\displaystyle\equiv\textsc{res}_{\mathcal{A}}(\mathsf{T},\mathsf{T})$
$\displaystyle\textsc{reach}_{\mathcal{A}}(\mathsf{T})$
$\displaystyle\equiv(\exists\mathsf{U}\subseteq\mathsf{S})(\textsc{res}_{\mathcal{A}}(\mathsf{U},\mathsf{T})\land\neg\textsc{res}_{\mathcal{A}}(\mathsf{T},\mathsf{U}))$
$\displaystyle\textsc{att}_{\mathcal{A}}(\mathsf{T})$
$\displaystyle\equiv\textsc{fix}_{\mathcal{A}}(\mathsf{T})\land\textsc{reach}_{\mathcal{A}}(\mathsf{T})$
$\displaystyle\textsc{fixge}_{\mathcal{A}}(\mathsf{T})$
$\displaystyle\equiv\textsc{fix}_{\mathcal{A}}(\mathsf{T})\land\neg\textsc{reach}_{\mathcal{A}}(\mathsf{T})$
$\displaystyle\textsc{res\textunderscore eq}_{\mathcal{A},\mathcal{B}}$
$\displaystyle\equiv(\forall\mathsf{T}\subseteq\mathsf{S})(\forall\mathsf{V}\subseteq\mathsf{S})(\textsc{res}_{\mathcal{A}}(\mathsf{T},\mathsf{V})\Leftrightarrow\textsc{res}_{\mathcal{B}}(\mathsf{T},\mathsf{V})).$

We say that a formula is $\mathsf{SO}\exists$, $\mathsf{SO}\forall$, or
$\mathsf{SO}\forall\exists$ if it is logically equivalent to a formula in the
required prenex normal form.

In Table 3, we give the logic formulae associated with the problems considered
in this work. The first six formulae were already given in [20]; we added the
last four to describe the new problems studied in this paper.

Problem | Formula | Logic class
---|---|---
$\exists$ fixed point | $(\exists\mathsf{T}\subseteq\mathsf{S})\textsc{fix}_{\mathcal{A}}(\mathsf{T})$ | $\mathsf{SO}\exists$
$\exists$ common fixed point | $(\exists\mathsf{T}\subseteq\mathsf{S})(\textsc{fix}_{\mathcal{A}}(\mathsf{T})\land\textsc{fix}_{\mathcal{B}}(\mathsf{T}))$ | $\mathsf{SO}\exists$
sharing all fixed points | $(\forall\mathsf{T}\subseteq\mathsf{S})(\textsc{fix}_{\mathcal{A}}(\mathsf{T})\Leftrightarrow\textsc{fix}_{\mathcal{B}}(\mathsf{T}))$ | $\mathsf{SO}\forall$
A given state is a fixed point attractor | $\textsc{att}_{\mathcal{A}}(\mathsf{T})$ | $\mathsf{SO}\exists$
$\exists$ fixed point attractor | $(\exists\mathsf{T}\subseteq\mathsf{S})\textsc{att}_{\mathcal{A}}(\mathsf{T})$ | $\mathsf{SO}\exists$
$\exists$ common fixed point attractor | $(\exists\mathsf{T}\subseteq\mathsf{S})\textsc{att}_{\mathcal{A}}(\mathsf{T})\land\textsc{att}_{\mathcal{B}}(\mathsf{T})$ | $\mathsf{SO}\exists$
sharing all fixed points attractors | $(\forall\mathsf{T}\subseteq\mathsf{S})(\textsc{att}_{\mathcal{A}}(\mathsf{T})\Leftrightarrow\textsc{att}_{\mathcal{B}}(\mathsf{T}))$ | $\mathsf{SO}\forall\exists$
$\exists$ fixed point not attractor | $(\exists\mathsf{T}\subseteq\mathsf{S})\textsc{fixge}(\mathsf{T})$ | $\mathsf{SO}\exists\forall$
$\exists$ common fixed point not attractor | $(\exists\mathsf{T}\subseteq\mathsf{S})(\textsc{fixge}_{\mathcal{A}}(\mathsf{T})\land\textsc{fixge}_{\mathcal{B}}(\mathsf{T}))$ | $\mathsf{SO}\exists\forall$
sharing all fixed points not attractors | $(\forall\mathsf{T}\subseteq\mathsf{S})(\textsc{fixge}_{\mathcal{A}}(\mathsf{T})\Leftrightarrow\textsc{fixge}_{\mathcal{B}}(\mathsf{T}))$ | $\mathsf{SO}\forall$
$\mathrm{res}_{\mathcal{A}}=\mathrm{res}_{\mathcal{B}}$ | $\textsc{res\textunderscore eq}_{\mathcal{A},\mathcal{B}}$ | $\mathsf{SO}\forall$

Table 3: Problems with the associated formula and logic class.

Remark that existential second-order logic $\mathsf{SO}\exists$ characterizes
NP (Fagin’s theorem [25]); universally quantified second-order logic
$\mathsf{SO}\forall$ gives coNP; second-order logic with one alternation of
existential and universal quantifiers $\mathsf{SO}\exists\forall$ gives
$\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$, and, in a dual way, second-order
logic with one alternation of universal and existential quantifiers
$\mathsf{SO}\forall\exists$ gives $\mathbf{\Pi}_{2}^{\textnormal{{P}}}$ [25].

The hardness proofs we give in this paper are obtained via reductions from
sat, validity [26] or $\forall\exists$sat [27]. In Definition 4 we introduce a
few sets of entities corresponding to a Boolean formula in CNF or DNF that
will be used in such proofs.

######  Definition 4.

Let $\varphi$ be a Boolean formula in CNF or DNF with clauses
$C=\\{\varphi_{1},\dots,\varphi_{m}\\}$ over the variables
$V=\\{x_{1},\dots,x_{n}\\}$. In the reductions, we will consider $V$ as a set
of entities representing true assignments to the variables and $C$ as a set of
entities representing the clauses. We also define the following additional
sets of entities.

$\overline{V}\coloneqq\\{\overline{x_{j}}:x_{j}\in V\\}$, entities
representing false assignments to the variables;
$\textnormal{pos}(\varphi_{r})\subseteq V$, representing the set of variables
that occur non-negated in $\varphi_{r}$ to which is assigned a true value;
$\textnormal{neg}(\varphi_{r})\subseteq V$, representing the set of variables
that occur negated in $\varphi_{r}$ to which is assigned a true value;
$\overline{\textnormal{pos}}(\varphi_{r})\subseteq\overline{V}$, representing
the set of variables that occur non-negated in $\varphi_{r}$ to which is
assigned a false value; and
$\overline{\textnormal{neg}}(\varphi_{r})\subseteq\overline{V}$, representing
the set of variables that occur negated in $\varphi_{r}$ to which is assigned
a false value.

In addition, we will use card suits symbols to denote extra entities that do
not belong to any of the sets defined above.

In general, in the reductions we will adopt the convention that overlining a
set of variables means that those variables are assigned a false value.
Indeed, the elements of the power set of $V$ and $\overline{V}$ are in a
natural bijection: thus for any $X\subseteq V$, $\overline{X}$ denotes the
assignment of a false value to the variables in $X$. In particular, we can
represent any assignment for $\varphi$ as a subset of entities
$X\cup\overline{V\setminus X}$, where $X\subseteq V$ is the subset of
variables that are set to true. Furthermore, $X\cup\overline{V\setminus
X}\vDash\varphi$ (resp.$X\cup\overline{V\setminus X}\nvDash\varphi$) means
that the assignment satisfies (resp. does not satisfy) $\varphi$.

##  4 A Given State is a Fixed Point Attractor

In this section, we study the problem of deciding whether a given state is a
fixed point attractor. The problem is NP-complete for
$\mathcal{RS}(\infty,\infty)$ [20, Theorem 4]; we prove that it remains so
also for reactantless and inhibitorless reaction systems.

######  Theorem 5.

Given $\mathcal{A}\in\mathcal{RS}(\infty,0)$ and a state $T\subseteq S$, it is
NP-complete to decide whether $T$ is a fixed point attractor.

###### Proof.

The problem is in NP (see Table 3). In order to show NP-hardness, we give a
reduction from sat [26]. Given a Boolean formula
$\varphi=\varphi_{1}\land\cdots\land\varphi_{m}$ in CNF over the variables
$V=\\{x_{1},\dots,x_{n}\\}$, we define a RS $\mathcal{A}$ with background set
$S\coloneqq V\cup\overline{V}\cup C\cup\\{\spadesuit\\}$, where
$C,V,\overline{V},\spadesuit$ are as in Definition 4, and reactions

$\displaystyle(\\{x\\},\varnothing,\\{\varphi_{j}\\})$ for $\displaystyle
1\leq j\leq m\text{ and }x\in\textnormal{pos}(\varphi_{j})$ (2)
$\displaystyle(\\{\overline{x}\\},\varnothing,\\{\varphi_{j}\\})$ for
$\displaystyle 1\leq j\leq m\text{ and
}\overline{x}\in\overline{\textnormal{neg}}(\varphi_{j})$ (3)
$\displaystyle(\\{x_{i},\overline{x_{i}}\\},\varnothing,\\{\spadesuit\\})$ for
$\displaystyle 1\leq i\leq n$ (4)
$\displaystyle(\\{x_{i},\varphi_{j}\\},\varnothing,\\{\spadesuit\\})$ for
$\displaystyle 1\leq i\leq n\text{ and }1\leq j\leq m$ (5)
$\displaystyle(\\{\overline{x_{i}},\varphi_{j}\\},\varnothing,\\{\spadesuit\\})$
for $\displaystyle 1\leq i\leq n\text{ and }1\leq j\leq m$ (6)
$\displaystyle(\\{\varphi_{j}\\},\varnothing,\\{\varphi_{j}\\})$ for
$\displaystyle 1\leq j\leq m$ (7)
$\displaystyle(\\{\spadesuit\\},\varnothing,\\{\spadesuit\\}).$ (8)

Reactions (7) imply that $T\coloneqq C$ is a fixed point for $\mathcal{A}$.
Furthermore, consider a state $T^{\prime}\neq C$ such that
$\mathrm{res}_{\mathcal{A}}(T^{\prime})\subseteq C$. It must hold
$T^{\prime}=X_{1}\cup\overline{X_{2}}$ with $X_{1}\subseteq V$,
$X_{2}\subseteq V$ and $X_{1}\cap X_{2}=\varnothing$, as otherwise
$\spadesuit$ would be generated by one of the reactions of type (4), (5), (6)
or (8). Furthermore, consider
$\varphi_{j}\in\mathrm{res}_{\mathcal{A}}(T^{\prime})$: since $T^{\prime}\cap
C=\varnothing$, then either
$X_{1}\cap\textnormal{pos}(\varphi_{j})\neq\varnothing$ or
$X_{2}\cap\textnormal{neg}(\varphi_{j})\neq\varnothing$ because at least one
of the reactions of type (2) or (3) with $\varphi_{j}$ in the product must be
enabled. We can thus interpret $T^{\prime}$ as an assignment satisfying
$\varphi$.

We remark that if $X_{1}\cup X_{2}\subsetneq V$, there must be some variables
that are irrelevant to the satisfiability of $\varphi$. Therefore, we proved
that if $C$ is an attractor then $\varphi$ is satisfiable. The converse
follows immediately, since if $X\subseteq V$ is the subset of variables that
are given a true value in an assignment that satisfies $\varphi$, then
$X\cup\overline{V\setminus X}$ enables at least one reaction of type (2) or
(3) for each clause, thus
$\mathrm{res}_{\mathcal{A}}(X\cup\overline{V\setminus X})=C$. We obtain that
$T=C$ is a fixed point attractor if and only if $\varphi$ is satisfiable. The
mapping $\varphi\mapsto(\mathcal{A},T)$ is clearly computable in polynomial
time, hence deciding if a given fixed point $T$ is an attractor is NP-hard. ∎

We highlight that all the reactions used in the proof of Theorem 5 involve at
most two reactants, implying that the problem is NP-complete even for the more
restricted class $\mathcal{RS}(2,0)$. Note, however, that if we are given a
fixed point of $\mathcal{A}$, it is in P to decide whether it is a special
kind of attractor: namely if it can be reached from one of its subsets or from
one of its supersets, as we prove in the following remark.

######  Remark 6.

Let $\mathcal{A}=(S,A)\in\mathcal{RS}(\infty,0)$ and $T$ be a fixed point for
$\mathrm{res}_{\mathcal{A}}$. If there exists $T^{\prime}\subsetneq T$ such
that $\mathrm{res}_{\mathcal{A}}(T^{\prime})=T$, then for all $x\in T\setminus
T^{\prime}$

$T=\mathrm{res}_{\mathcal{A}}(T^{\prime})\subseteq\mathrm{res}_{\mathcal{A}}(T\setminus\\{x\\})\subseteq\mathrm{res}_{\mathcal{A}}(T)=T,$

thus $T$ is reachable from $T\setminus\\{x\\}$; and if there exists
$T^{\prime\prime}\supsetneq T$ such that
$\mathrm{res}_{\mathcal{A}}(T^{\prime\prime})=T$, then for all $x\in
T^{\prime\prime}\setminus T$

$T=\mathrm{res}_{\mathcal{A}}(T)\subseteq\mathrm{res}_{\mathcal{A}}(T\cup\\{x\\})\subseteq\mathrm{res}_{\mathcal{A}}(T^{\prime\prime})=T,$

thus $T$ is reachable from $T\cup\\{x\\}$. To decide whether $T$ is an
attractor of the form $T^{\prime}$ and $T^{\prime\prime}$ it thus suffices to
check, for all $x\in S$, whether $T$ is reachable from $T\setminus\\{x\\}$ or
$T\cup\\{x\\}$, and it thus requires polynomial time.

######  Theorem 7.

Given $\mathcal{A}\in\mathcal{RS}(0,\infty)$ and a state $T\subseteq S$, it is
NP-complete to decide whether $T$ is a fixed point attractor.

###### Proof.

The problem is in NP (see Table 3). In order to show NP-hardness, we give a
reduction from sat [26]. Given a Boolean formula
$\varphi=\varphi_{1}\land\cdots\land\varphi_{m}$ in CNF over the variables
$V=\\{x_{1},\dots,x_{n}\\}$, we define $\mathcal{A}$ a RS with background set
$S\coloneqq V\cup\overline{V}\cup
C\cup\\{\clubsuit,\diamondsuit,\spadesuit\\}$, where each set is as defined in
Definition 4, and the set of reactions is

$\displaystyle(\varnothing,\\{\overline{x},\clubsuit,\spadesuit\\},\\{\varphi_{j}\\})$
for $\displaystyle 1\leq j\leq m\text{ and
}\overline{x}\in\overline{\textnormal{pos}}(\varphi_{j})$ (9)
$\displaystyle(\varnothing,\\{x,\clubsuit,\spadesuit\\},\\{\varphi_{j}\\})$
for $\displaystyle 1\leq j\leq m\text{ and }x\in\textnormal{neg}(\varphi_{j})$
(10)
$\displaystyle(\varnothing,\\{x_{i},\overline{x_{i}},\clubsuit,\spadesuit\\},\\{\spadesuit\\})$
for $\displaystyle 1\leq i\leq n$ (11)
$\displaystyle(\varnothing,\\{\varphi_{j}\\},\\{\spadesuit\\})$ for
$\displaystyle 1\leq j\leq m$ (12)
$\displaystyle(\varnothing,S\setminus(C\cup\\{\clubsuit\\}),C)$ (13)
$\displaystyle(\varnothing,\\{\diamondsuit,\spadesuit\\},\\{\clubsuit\\})$
(14) $\displaystyle(\varnothing,\\{\clubsuit,\spadesuit\\},\\{\clubsuit\\})$
(15)
$\displaystyle(\varnothing,\\{\clubsuit,\diamondsuit\\},\\{\clubsuit,\diamondsuit,\spadesuit\\})$
(16)

By reactions (13) and (14), $T\coloneqq C\cup\\{\clubsuit\\}$ is a fixed point
for $\mathcal{A}$. Let $T^{\prime}\neq C\cup\\{\clubsuit\\}$ such that
$\mathrm{res}_{\mathcal{A}}(T^{\prime})=C\cup\\{\clubsuit\\}$, then
$C\subseteq T^{\prime}$, otherwise
$\spadesuit\in\mathrm{res}_{\mathcal{A}}(T^{\prime})$ because of the reactions
of type (12). In order to have
$\mathrm{res}_{\mathcal{A}}(T^{\prime})\cap\\{\clubsuit,\diamondsuit,\spadesuit\\}=\\{\clubsuit\\}$,
$T^{\prime}$ must either satisfy
$T^{\prime}\cap\\{\clubsuit,\diamondsuit,\spadesuit\\}=\\{\clubsuit\\}$ or
$T^{\prime}\cap\\{\clubsuit,\diamondsuit,\spadesuit\\}=\\{\diamondsuit\\}$
(see Figure 1). We prove by contradiction that the first case cannot occur:
indeed, in this case, the only reactions enabled by $T^{\prime}$ are (13) and
(14). Since adding any element of $V\cup\overline{V}$ to $T^{\prime}$ would
disable (13) and we have $C\subseteq\mathrm{res}_{\mathcal{A}}(T^{\prime})$,
we deduce that we would have $T^{\prime}=C\cup\\{\clubsuit\\}$, a
contradiction. Therefore $T^{\prime}$ must be of the form
$X_{1}\cup\overline{X_{2}}\cup C\cup\\{\diamondsuit\\}$, where $X_{1}\subseteq
V$ and $\overline{X_{2}}\subseteq\overline{V}$. If we had $X_{1}\cup
X_{2}\subsetneq V$ then we would also have
$\spadesuit\in\mathrm{res}_{\mathcal{A}}(T^{\prime})$ because one of the
reactions (11) would be enabled; thus it must hold $X_{1}\cup X_{2}=V$.

If $x\in X_{1}\cap X_{2}$ then neither $x$ nor $\overline{x}$ will be able to
generate any $\varphi_{j}$ because of reactions (9) and (10); however, since
$C\subseteq\mathrm{res}_{\mathcal{A}}(T^{\prime})$, for each $\varphi_{j}\in
C$ there must exist a $x\in V$ such that either $x\in X_{1}$ or
$\overline{x}\in\overline{X_{2}}$ satisfies $\varphi_{j}$. Therefore, we
proved that if $C\cup\\{\clubsuit\\}$ is an attractor then $\varphi$ is
satisfiable. The converse follows immediately, since if $X\subseteq V$ are the
variables set to true in an assignment satisfying $\varphi$, then
$X\cup\overline{V\setminus X}\cup C\cup\\{\diamondsuit\\}$ is a state
attracted by $C\cup\\{\clubsuit\\}$. We obtain that $T=C\cup\\{\clubsuit\\}$
is a fixed point attractor if and only if $\varphi$ is satisfiable. The
mapping $\varphi\mapsto(\mathcal{A},T)$ is computable in polynomial time,
hence deciding if a given fixed point $T$ is an attractor is NP-hard. ∎

Figure 1: Graph representation of the dynamics given by the reactions (14),
(15), (16) over the subset of the background set
$\\{\clubsuit,\diamondsuit,\spadesuit\\}$.

##  5 Fixed Points for Reactantless RS

In this section, we prove NP-hardness, coNP-hardness,
$\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$-hardness and
$\mathbf{\Pi}_{2}^{\textnormal{{P}}}$-hardness for problems of fixed points in
the class of reactantless RS.

The problem of deciding if there exists a fixed point is NP-complete for
$\mathcal{RS}(\infty,\infty)$ [20, Theorem 2]; the following theorem shows
that it remains difficult also in $\mathcal{RS}(0,\infty)$.

######  Theorem 8.

Given $\mathcal{A}\in\mathcal{RS}(0,\infty)$, it is NP-complete to decide if
$\mathcal{A}$ has a fixed point.

###### Proof.

The problem is in NP (see Table 3). In order to show NP-hardness, we reduce
sat [26] to this problem. Given a Boolean formula
$\varphi=\varphi_{1}\land\cdots\land\varphi_{m}$ in CNF over the variables
$V=\\{x_{1},\dots,x_{n}\\}$, we define a RS $\mathcal{A}$ with background set
$S\coloneqq V\cup\overline{V}\cup\\{\spadesuit\\}\cup\\{\clubsuit\\}$ (the
sets are as in Definition 4) and the reactions

$\displaystyle(\varnothing,\overline{\textnormal{neg}}(\varphi_{j})\cup\textnormal{pos}(\varphi_{j}),\\{\spadesuit\\})$
for $\displaystyle 1\leq j\leq m$ (17)
$\displaystyle\overline{a_{i}}\coloneqq$
$\displaystyle(\varnothing,\\{x_{i}\\},\\{\overline{x_{i}}\\})$ for
$\displaystyle 1\leq i\leq n$ (18) $\displaystyle a_{i}\coloneqq$
$\displaystyle(\varnothing,\\{\overline{x_{i}}\\},\\{x_{i}\\})$ for
$\displaystyle 1\leq i\leq n$ (19)
$\displaystyle(\varnothing,\\{\clubsuit\\},\\{\clubsuit,\spadesuit\\})$ (20)
$\displaystyle(\varnothing,\\{\spadesuit\\},\\{\clubsuit\\}).$ (21)

Given a state $T\subseteq S$, let $T_{V}=T\cap V$ and
$T_{\overline{V}}=T\cap\overline{V}$. When $x_{j}\in
T_{V}\Leftrightarrow\overline{x_{j}}\notin T_{\overline{V}}$ for every $j$,
then $T_{V}\cup T_{\overline{V}}$ encodes an assignment of $\varphi$ in which
the variables having true value are those in $T_{V}$ and the variables having
false value are those in $T_{\overline{V}}$. In this case we say that $T$ is a
well-formed state of $\mathcal{A}$ and the reactions of type (18),(19)
preserve $T_{V}\cup T_{\overline{V}}$, i.e., $T_{V}\cup
T_{\overline{V}}\subseteq\mathrm{res}_{\mathcal{A}}(T)$. Instead, if $T$ is
not a well-formed state then we distinguish two cases:

  * •

if $\exists x_{i},\overline{x_{i}}\in T_{V}\cup T_{\overline{V}}$ then
$x_{i},\overline{x_{i}}\notin\mathrm{res}_{\mathcal{A}}(T)$, since neither
$a_{i}$ nor $\overline{a_{i}}$ is enabled;

  * •

if $\exists x_{i},\overline{x_{i}}\notin T_{V}\cup T_{\overline{V}}$ then
$x_{i},\overline{x_{i}}\in\mathrm{res}_{\mathcal{A}}(T)$, since both $a_{i}$
and $\overline{a_{i}}$ are enabled.

In both cases, $T\neq\mathrm{res}_{\mathcal{A}}(T)$; so if $T$ is a fixed
point, $T$ is a well-formed state. For well-formed states, we can also give an
interpretation of the reactions of type (17): they evaluate each disjunctive
clause (which is not satisfied if and only if no positive variables are set to
true and no negative ones to false) and generate $\spadesuit$ when $\varphi$
itself is not satisfied by $T_{V}\cup T_{\overline{V}}$.

Consider the dynamic of the reaction system restricted to a well-formed state
$Y\subseteq V\cup\overline{V}$. If $Y$ does not satisfy $\varphi$ then there
are no fixed points among the well-formed states containing $Y$ because of the
following (the arrows represent function $\mathrm{res}_{\mathcal{A}}$):

${Y}$${Y\cup\\{\clubsuit,\spadesuit\\}}$${Y\cup\\{\spadesuit\\}}$${Y\cup\\{\clubsuit\\}}$

Instead, if $Y$ satisfies $\varphi$, then $Y\cup\\{\clubsuit\\}$ is a fixed
point since:

${Y\cup\\{\spadesuit\\}}$${Y\cup\\{\clubsuit,\spadesuit\\}}$${Y}$${Y\cup\\{\clubsuit\\}}$

In particular, $\mathcal{A}$ has a fixed point if and only $\varphi$ is
satisfiable. The mapping $\varphi\mapsto\mathcal{A}$ is computable in
polynomial time, hence deciding on the existence of fixed points for
reactantless RS is NP-hard. ∎

As an immediate consequence of Theorem 8 we obtain that deciding if there
exists a state that is a common fixed point of two reactantless reaction
systems remains NP-complete.

######  Corollary 9.

Given $\mathcal{A},\mathcal{B}\in\mathcal{RS}(0,\infty)$ with a common
background set $S$, it is NP-complete to decide whether $\mathcal{A}$ and
$\mathcal{B}$ have a common fixed point.

###### Proof.

The problem is in NP (see Table 3). By Theorem 8, when
$\mathcal{A}=\mathcal{B}$ the problem is NP-complete. ∎

With a small adaptation of the proof of Theorem 8, deciding if a fixed point
attractor exists is still an NP-complete problem. The NP-completeness for
$\mathcal{RS}(\infty,\infty)$ is proved in [20, Corollary 3]; the following
theorem proves it for the case of reactantless systems.

######  Theorem 10.

Given $\mathcal{A}=(S,A)\in\mathcal{RS}(0,\infty)$, it is NP-complete to
decide if $\mathcal{A}$ has a fixed point attractor.

###### Proof.

The problem is in NP, as highlighted in Table 3. In order to show NP-hardness,
we reduce sat [26] to this problem. Given a Boolean formula
$\varphi=\varphi_{1}\land\cdots\land\varphi_{m}$ in CNF, we construct the same
reaction system $\mathcal{A}$ of Theorem 8 and we substitute reaction (20)
with $(\varnothing,\\{\clubsuit\\},\\{\clubsuit\\})$. In this way, if
$Y\subseteq V\cup\overline{V}$ is a well-formed state satisfying $\varphi$ we
have:

${Y\cup\\{\clubsuit,\spadesuit\\}}$${Y}$${Y\cup\\{\clubsuit\\}}$${Y\cup\\{\spadesuit\\}}$

which means that $Y\cup\\{\clubsuit\\}$ is a fixed point reachable from $Y$ or
$Y\cup\\{\spadesuit\\}$. In the other cases (either a well-formed state not
satisfying $\varphi$ or a not well-formed state), $T\subseteq S$ is never a
fixed point, as in the proof of Theorem 8. Since the mapping
$\varphi\mapsto\mathcal{A}$ is computable in polynomial time, deciding on the
existence of a fixed points attractor for reactantless RS is NP-hard. ∎

######  Corollary 11.

Given $\mathcal{A},\mathcal{B}\in\mathcal{RS}(0,\infty)$ with a common
background set $S$, it is NP-complete to decide whether $\mathcal{A}$ and
$\mathcal{B}$ have a common fixed point attractor.

###### Proof.

The problem is in NP (see Table 3). By Theorem 10, when
$\mathcal{A}=\mathcal{B}$ the problem is NP-hard. ∎

In contrast, if we consider the existence of a fixed point not attractor the
problem is in $\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$; the following theorem
proves the $\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$-hardness.

######  Theorem 12.

Given $\mathcal{A}\in\mathcal{RS}(0,\infty)$, it is
$\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$-complete to decide if $\mathcal{A}$
has a fixed point which is not an attractor.

###### Proof.

The problem is in $\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$ (see Table 3).
Consider the converse problem, i.e. decide if all fixed points are attractors.
In order to show $\mathbf{\Pi}_{2}^{\textnormal{{P}}}$-hardness of the latter,
we construct a reduction from $\forall\exists$sat [27]. Given a quantified
Boolean formula $(\forall V_{1})(\exists V_{2})\varphi$ over
$V=\\{x_{1},\dots,x_{n}\\}$, with $V_{1}\subseteq V$, $V_{2}=V\setminus V_{1}$
and $\varphi=\varphi_{1}\land\cdots\land\varphi_{m}$ quantifier-free and in
CNF, let $\heartsuit_{S}\coloneqq\\{\heartsuit_{i}:1\leq i\leq n\\}$ be a set
of extra entities that are not contained in $V\cup\overline{V}\cup C$ and
$V,\overline{V},C$ are as in Definition 4. We define a RS $\mathcal{A}$ with
background set $S\coloneqq V\cup\overline{V}\cup
C\cup\heartsuit_{S}\cup\\{\clubsuit,\diamondsuit,\spadesuit\\}$ and the
reactions

$\displaystyle(\varnothing,\\{\overline{x},\clubsuit,\spadesuit\\},\\{\varphi_{j}\\})\>\quad\quad\qquad\qquad\qquad\text{for
}\varphi_{j}\in C$ and
$\displaystyle\overline{x}\in\overline{\textnormal{pos}}(\varphi_{j})$ (22)
$\displaystyle(\varnothing,\\{x,\clubsuit,\spadesuit\\},\\{\varphi_{j}\\})\>\quad\quad\qquad\qquad\qquad\text{for
}\varphi_{j}\in C$ and $\displaystyle x\in\textnormal{neg}(\varphi_{j})$ (23)
$\displaystyle(\varnothing,\overline{\textnormal{neg}}(\varphi_{j})\cup\textnormal{pos}(\varphi_{j})\cup\\{\clubsuit,\spadesuit\\},\\{\spadesuit\\})$
for $\displaystyle 1\leq j\leq m$ (24)
$\displaystyle(\varnothing,\\{x_{i},\clubsuit,\spadesuit\\},\\{\heartsuit_{i}\\})$
for $\displaystyle 1\leq i\leq n$ (25)
$\displaystyle(\varnothing,\\{\overline{x_{i}},\clubsuit,\spadesuit\\},\\{\heartsuit_{i}\\})$
for $\displaystyle 1\leq i\leq n$ (26)
$\displaystyle(\varnothing,\\{x_{i},\overline{x_{i}},\clubsuit,\spadesuit\\},\\{\spadesuit\\})$
for $\displaystyle 1\leq i\leq n$ (27)
$\displaystyle(\varnothing,\\{\varphi_{j}\\},\\{\spadesuit\\})$ for
$\displaystyle 1\leq j\leq m$ (28)
$\displaystyle(\varnothing,\\{\heartsuit_{i}\\},\\{\spadesuit\\})$ for
$\displaystyle 1\leq i\leq n$ (29)
$\displaystyle(\varnothing,\\{\overline{x}\\},\\{x\\})$ for $\displaystyle
x\in V_{1}$ (30) $\displaystyle(\varnothing,\\{x\\},\\{\overline{x}\\})$ for
$\displaystyle x\in V_{1}$ (31)
$\displaystyle(\varnothing,S\setminus(C\cup\heartsuit_{S}\cup\\{\clubsuit\\}\cup
V_{1}\cup\overline{V_{1}}),C\cup\heartsuit_{S})$ (32)
$\displaystyle(\varnothing,\\{\diamondsuit,\spadesuit\\},\\{\clubsuit\\})$
(33) $\displaystyle(\varnothing,\\{\clubsuit,\spadesuit\\},\\{\clubsuit\\})$
(34)
$\displaystyle(\varnothing,\\{\clubsuit,\diamondsuit\\},\\{\clubsuit,\diamondsuit,\spadesuit\\}).$
(35)

To study the dynamics of $\mathcal{A}$ we first analyze the form of its fixed
points.

######  Claim 13.

If $T$ is a fixed point of $\mathcal{A}$, then $\clubsuit\in T$,
$\diamondsuit\notin T$ and $\spadesuit\notin T$.

###### Proof.

If we had $\diamondsuit\in T$, then the only reaction that can produce
$\diamondsuit$, i.e., reaction (35), is not enabled, thus
$\diamondsuit\notin\mathrm{res}_{\mathcal{A}}(T)=T$, a contradiction. If we
had $\spadesuit\in T$ and $\clubsuit\notin T$, then
$\\{\clubsuit,\diamondsuit\\}\subseteq\mathrm{res}_{\mathcal{A}}(T)=T$ by
reaction (35), a contradiction. If we had $\spadesuit\in T$ and $\clubsuit\in
T$, no reaction that can produce $\clubsuit$ would be enabled (reactions (33),
(34), (35)), a contradiction. Therefore, it must hold $\diamondsuit\notin T$
and $\spadesuit\notin T$; if in addition we had $\clubsuit\notin T$, then
reaction (35) would be enabled and thus we would have
$\\{\clubsuit,\diamondsuit,\spadesuit\\}\subseteq\mathrm{res}_{\mathcal{A}}(T)=T$,
a contradiction. For a visual representation of the dynamics of reactions
(33), (34), (35) see Figure 1. The statement follows. ∎

######  Claim 14.

The fixed points of $\mathcal{A}$ are the states of type

$T_{U}\coloneqq C\cup\heartsuit_{S}\cup U\cup\overline{V_{1}\setminus
U}\cup\\{\clubsuit\\},$ (36)

for any $U\subseteq V_{1}$.

###### Proof.

Let $T$ be a fixed point for $\mathcal{A}$; by Claim 13 and looking at the
products of the reactions it must be $T\subseteq C\cup\heartsuit_{S}\cup
V_{1}\cup\overline{V_{1}}\cup\\{\clubsuit\\}$ with $\clubsuit\in T$. Moreover,
if we had $C\cap T\subsetneq C$ then at least one of the reactions of group
(28) would be enabled, thus it would be
$\spadesuit\in\mathrm{res}_{\mathcal{A}}(T)=T$, a contradiction. If we had
$\heartsuit_{S}\cap T\subsetneq\heartsuit_{S}$ then at least one of the
reactions of group (29) would be enabled, thus we would have
$\spadesuit\in\mathrm{res}_{\mathcal{A}}(T)=T$, a contradiction. By reactions
(30), (31) and (27), arguing as in the proof of Theorem 8, we get that $T$
must be a well-formed state for $V_{1}\cup\overline{V_{1}}$, i.e., $x\in T\cap
V_{1}$ if and only if $\overline{x}\notin T\cap\overline{V_{1}}$. Therefore,
$T$ is of type (36) with $U=T\cap V_{1}$. Finally, we can immediately check
that if a state is of type (36), then it is a fixed point because of reactions
(30), (31) and (32). ∎

We are now interested in studying when a fixed point $T_{U}$, for a given
$U\subseteq V_{1}$, is an attractor. Let $T^{\prime}\neq T_{U}$ such that
$\mathrm{res}_{\mathcal{A}}(T^{\prime})=T_{U}$. If it was $C\cap
T^{\prime}\subsetneq C$ then at least one of the reactions of group (28) would
be enabled, thus it would be
$\spadesuit\in\mathrm{res}_{\mathcal{A}}(T^{\prime})=T$, a contradiction; and
if it was $\heartsuit_{S}\cap T^{\prime}\subsetneq\heartsuit_{S}$ then at
least one of the reactions of group (29) would be enabled, thus it would be
$\spadesuit\in\mathrm{res}_{\mathcal{A}}(T^{\prime})=T$, a contradiction.
Therefore it must be $C\cup\heartsuit_{S}\subseteq T^{\prime}$.

######  Claim.

If $T^{\prime}\neq T_{U}$ and $\mathrm{res}_{\mathcal{A}}(T^{\prime})=T_{U}$
then $\clubsuit\notin T^{\prime}$, $\diamondsuit\in T^{\prime}$ and
$\spadesuit\notin T^{\prime}$.

###### Proof.

If we had $\spadesuit\in T^{\prime}$ then reactions (22), (23) and (32) would
not be enabled, thus we would have
$C\cap\mathrm{res}_{\mathcal{A}}(T^{\prime})=\varnothing$, a contradiction
since $C\subseteq T_{U}=\mathrm{res}_{\mathcal{A}}(T^{\prime})$. Therefore we
obtain $\spadesuit\notin T^{\prime}$. If we had $\clubsuit\in T^{\prime}$ we
divide two cases:

  * •

if $\diamondsuit\in T^{\prime}$ then none of the reactions (33), (34), (35)
would be enabled, therefore we would have
$\clubsuit\notin\mathrm{res}_{\mathcal{A}}(T^{\prime})=T_{U}$, a
contradiction.

  * •

if $\diamondsuit\notin T^{\prime}$, the only way to get
$C\subseteq\mathrm{res}_{\mathcal{A}}(T^{\prime})$ would be with reaction
(32), since (22), (23) are not enabled if $\clubsuit\in T^{\prime}$. Therefore
to enable (32), we must have $T^{\prime}\subseteq
C\cup\heartsuit_{S}\cup\\{\clubsuit\\}\cup V_{1}\cup\overline{V_{1}}$, and
since $C\cup\heartsuit_{S}\subseteq T^{\prime}$, as previously remarked, we
obtain $T^{\prime}=C\cup\heartsuit_{S}\cup\\{\clubsuit\\}\cup
U_{1}\cup\overline{U_{2}}$ for some $U_{1}\subseteq V_{1}$ and $U_{2}\subseteq
V_{1}$. Since $\mathrm{res}_{\mathcal{A}}(T^{\prime})=T_{U}$ contains a well-
formed state for $V_{1}\cup\overline{V_{1}}$, then $U_{1}\cup\overline{U_{2}}$
must be a well-formed state for $V_{1}\cup\overline{V_{1}}$. In this case we
would obtain
$\mathrm{res}_{\mathcal{A}}(T^{\prime})=C\cup\heartsuit_{S}\cup\\{\clubsuit\\}\cup
U_{1}\cup\overline{U_{2}}$, hence we would have $U_{1}=U$, $U_{2}=V\setminus
U$ and thus $T^{\prime}=T_{U}$, a contradiction.

Therefore $\clubsuit\notin T^{\prime}$. Finally, if $\diamondsuit\notin
T^{\prime}$ then
$\\{\clubsuit,\diamondsuit,\spadesuit\\}\subseteq\mathrm{res}_{\mathcal{A}}(T^{\prime})=T_{U}$
(35), a contradiction. The statement follows. ∎

By previous claim and remarks, we obtain that if $T^{\prime}\neq T_{U}$ is an
attractor for $T_{U}$ then it must be of the form
$T^{\prime}=C\cup\heartsuit_{S}\cup\\{\diamondsuit\\}\cup
X_{1}\cup\overline{X_{2}}$ for some $X_{1}\subseteq V$ and $X_{2}\subseteq V$.
In this case, reaction (32) is not enabled, thus the fact that
$C\cup\heartsuit_{S}\subseteq\mathrm{res}_{\mathcal{A}}(T^{\prime})=T_{U}$
will only depend on how $X_{1}\cup\overline{X_{2}}$ is constructed. We
consider two cases:

  * •

if $\exists x_{i},\overline{x_{i}}\in X_{1}\cup\overline{X_{2}}$ then
$\heartsuit_{i}\notin\mathrm{res}_{\mathcal{A}}(T^{\prime})$, since neither
the $i$-th reaction of (25) nor the $i$-th reaction of (26) are enabled;

  * •

if $\exists x_{i},\overline{x_{i}}\notin X_{1}\cup\overline{X_{2}}$ then
$\spadesuit\in\mathrm{res}_{\mathcal{A}}(T^{\prime})$, since the $i$-th
reaction in (27) is enabled.

Therefore $X_{1}\cup\overline{X_{2}}$ must be a well-formed state for
$V\cup\overline{V}$, and thus $X_{2}=V\setminus X_{1}$. We can interpret
$X_{1}\cup\overline{V\setminus X_{1}}$ as an assignment for $\varphi$, as in
the proof of Theorem 8. If we had $X_{1}\cup\overline{V\setminus
X_{1}}\nvDash\varphi$, then one of the reactions (24) would be enabled, thus
we would have $\spadesuit\in\mathrm{res}_{\mathcal{A}}(T^{\prime})$, a
contradiction. Therefore it must hold $X_{1}\cup\overline{V\setminus
X_{1}}\vDash\varphi$, thus all clauses are satisfied, i.e., each
$\varphi_{j}\in C$ is generated by at least one reaction of type (34) or (35).
We obtain

$\mathrm{res}_{\mathcal{A}}(T^{\prime})=C\cup\heartsuit_{S}\cup\\{\clubsuit\\}\cup\\{x:x\in
X_{1}\cap
V_{1}\\}\cup\\{\overline{x}:\overline{x}\in\overline{X_{2}}\cap\overline{V_{1}}\\}=T_{U}$

thus $U=X_{1}\cap V_{1}$, and therefore if $T_{U}$ is an attractor there
exists an assignment for $\varphi$ such that all variables in $U$ are set to
true. The converse is also true, i.e., if there exists an assignment
$X\cup\overline{V\setminus X}$ such that $U\subseteq X$ and $\varphi$ is
satisfied then $T_{U}$ is reached by
$C\cup\heartsuit_{S}\cup\\{\diamondsuit\\}\cup X\cup\overline{V\setminus X}$.
Finally, all the fixed points of $\mathcal{A}$ are attractors if and only if
$(\forall V_{1})(\exists V_{2})\varphi$ is valid.

The mapping $\varphi\mapsto\mathcal{A}$ is computable in polynomial time,
hence deciding if all the fixed points of $\mathcal{A}$ are attractors is
$\mathbf{\Pi}_{2}^{\textnormal{{P}}}$-hard. Therefore, deciding if
$\mathcal{A}$ has a fixed point which is not attractor is
$\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$-hard. ∎

######  Corollary 15.

Given $\mathcal{A},\mathcal{B}\in\mathcal{RS}(0,\infty)$ with a common
background set $S$, it is $\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$-complete to
decide whether $\mathcal{A}$ and $\mathcal{B}$ have a common fixed point which
is not an attractor.

###### Proof.

The problem is in $\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$ (see Table 3); by
Theorem 12, when $\mathcal{A}=\mathcal{B}$ the problem is
$\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$-complete. ∎

Since the problems are $\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$-complete for
$\mathcal{RS}(0,\infty)$, we have that they are also
$\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$-complete for
$\mathcal{RS}(\infty,\infty)$, as stated by the following corollaries.

######  Corollary 16.

Given $\mathcal{A}=(S,A)\in\mathcal{RS}(\infty,\infty)$, it is
$\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$-complete to decide if $\mathcal{A}$
has a fixed point which is not an attractor.

######  Corollary 17.

Given $\mathcal{A},\mathcal{B}\in\mathcal{RS}(\infty,\infty)$ with a common
background set $S$, it is $\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$-complete to
decide whether $\mathcal{A}$ and $\mathcal{B}$ have a common fixed point which
is not an attractor.

We now study the problem of deciding if two reaction systems share all their
fixed point attractors.

######  Corollary 18.

Given $\mathcal{A},\mathcal{B}\in\mathcal{RS}(0,\infty)$ with a common
background set $S$, it is $\mathbf{\Pi}_{2}^{\textnormal{{P}}}$-complete to
decide whether $\mathcal{A}$ and $\mathcal{B}$ share all their fixed point
attractors.

###### Proof.

The problem is in $\mathbf{\Pi}_{2}^{\textnormal{{P}}}$ (see Table 3). In
order to show $\mathbf{\Pi}_{2}^{\textnormal{{P}}}$-hardness, we reduce
$\forall\exists$sat [27] to this problem. Consider the reaction system
$\mathcal{A}$ in the proof of Theorem 12; we just need to construct a RS
$\mathcal{B}$ over the same background set as $\mathcal{A}$ such that all the
fixed points attractors of $\mathcal{B}$ are of the form $T_{U}$ for any
$U\subseteq V_{1}$. Therefore we define the reactions of $\mathcal{B}$ to be
the reactions (28), (29), (30), (31), (32), (33), (34) and (35) from the proof
of Theorem 12. We remark that Claims 13 and 14 can be applied to
$\mathcal{B}$, therefore all the fixed points of $\mathcal{B}$ are the states
$T_{U}$ for any $U\subseteq V_{1}$. Furthermore, all the fixed points of
$\mathcal{B}$ are attractors and coincide with the ones of $\mathcal{A}$. The
mapping $\varphi\mapsto(\mathcal{A},\mathcal{B})$ is computable in polynomial
time, hence deciding if two RS share all their fixed point attractors is
$\mathbf{\Pi}_{2}^{\textnormal{{P}}}$-hard. ∎

We now study the problem of deciding whether two reaction systems share all
their fixed points. The problem is coNP-complete for
$\mathcal{RS}(\infty,\infty)$ [20, Theorem 3], and this is also true for
reactantless reaction systems, as proved in the following theorem.

######  Theorem 19.

Given $\mathcal{A},\mathcal{B}\in\mathcal{RS}(0,\infty)$ with a common
background set $S$, it is coNP-complete to decide whether $\mathcal{A}$ and
$\mathcal{B}$ share all their fixed points.

###### Proof.

The problem lies in coNP (see Table 3). In order to show coNP-completeness, we
reduce validity [26] to this problem. Given a Boolean formula
$\varphi=\varphi_{1}\lor\cdots\lor\varphi_{m}$ in DNF over the variables
$V=\\{x_{1},\dots,x_{n}\\}$, we define a RS $\mathcal{A}$ with background set
$S\coloneqq V\cup\overline{V}\cup\\{\heartsuit\\}\cup\\{\clubsuit\\}$ (where
the sets are as in Definition 4) and the reactions:

$\displaystyle(\varnothing,\textnormal{neg}(\varphi_{j})\cup\overline{\textnormal{pos}}(\varphi_{j})\cup\\{\clubsuit\\},\\{\heartsuit\\})$
for $\displaystyle 1\leq j\leq m$ (37)
$\displaystyle(\varnothing,\\{x_{i}\\},\\{\overline{x_{i}}\\})$ for
$\displaystyle 1\leq i\leq n$ (38)
$\displaystyle(\varnothing,\\{\overline{x_{i}}\\},\\{x_{i}\\})$ for
$\displaystyle 1\leq i\leq n$ (39)
$\displaystyle(\varnothing,\\{\heartsuit\\},\\{\heartsuit,\clubsuit\\}).$ (40)

As in the proof of Theorem 8, if $T$ is not a well-formed state then $T$ is
not a fixed point. Reactions of type (37) evaluate each conjunctive clause
(which is satisfied if and only if no positive variables are set to false and
no negative ones to true) and generate $\heartsuit$ when $\varphi$ itself is
satisfied by $T\cap(V\cup\overline{V})$. Consider the dynamic of the reaction
system restricted to a well-formed state $Y\subseteq V\cup\overline{V}$. If
$Y$ does not satisfy $\varphi$ there are no fixed points since:

${Y\cup\\{\heartsuit\\}}$${Y}$${Y\cup\\{\heartsuit,\clubsuit\\}}$${Y\cup\\{\clubsuit\\}}$

where the arrow represent the function $\mathrm{res}_{\mathcal{A}}$. Instead,
if $Y$ satisfies $\varphi$, $Y\cup\\{\heartsuit\\}$ is a fixed point since:

${Y\cup\\{\heartsuit\\}}$${Y}$${Y\cup\\{\heartsuit,\clubsuit\\}}$${Y\cup\\{\clubsuit\\}.}$

Finally, the fixed points of $\mathcal{A}$ are the well-formed states
$Y\cup\\{\heartsuit\\}$ such that $Y\vDash\varphi$. Now, let $\mathcal{B}$ be
defined by the following reactions:

$\displaystyle(\varnothing,\\{x_{i}\\},\\{\overline{x_{i}}\\})$ for
$\displaystyle 1\leq i\leq n$
$\displaystyle(\varnothing,\\{\overline{x_{i}}\\},\\{x_{i}\\})$ for
$\displaystyle 1\leq i\leq n$
$\displaystyle(\varnothing,\\{\clubsuit\\},\\{\heartsuit\\})$
$\displaystyle(\varnothing,\\{\heartsuit\\},\\{\heartsuit,\clubsuit\\}).$

In a similar way as above, the fixed points of $\mathcal{B}$ are the states
$Y\cup\\{\heartsuit\\}$ where $Y\subseteq V\cup\overline{V}$ is well-formed.
We can conclude that $\mathcal{A}$ and $\mathcal{B}$ share all fixed points
exactly when all assignments satisfy $\varphi$, i.e., $\varphi$ is a
tautology. Since the mapping $\varphi\mapsto(\mathcal{A},\mathcal{B})$ is
computable in polynomial time, the problem is coNP-hard. ∎

Note that in the proof of Theorem 19, the fixed points of $\mathcal{A}$ and
$\mathcal{B}$ are not attractors: this implies the following result.

######  Corollary 20.

Given $\mathcal{A},\mathcal{B}\in\mathcal{RS}(0,\infty)$ with a common
background set $S$, it is coNP-complete to decide whether $\mathcal{A}$ and
$\mathcal{B}$ share all their fixed points which are not attractors.

Since the problem is coNP-complete for $\mathcal{RS}(0,\infty)$, we have that
it is also coNP-complete for $\mathcal{RS}(\infty,\infty)$, as stated by the
following corollary.

######  Corollary 21.

Given $\mathcal{A},\mathcal{B}\in\mathcal{RS}(\infty,\infty)$ with a common
background set $S$, it is coNP-complete to decide whether $\mathcal{A}$ and
$\mathcal{B}$ share all their fixed points which are not attractors.

##  6 Fixed Points for Inhibitorless RS

In this section, we prove NP-hardness and coNP-hardness for problems of fixed
points in the class of inhibitorless RS.

The problem of deciding the existence of a fixed point is entirely trivial for
$\mathcal{RS}(\infty,0)$ thanks to the Knaster-Tarski theorem, as first
remarked in [23]. On the contrary, the following theorem shows that it is NP-
complete to decide whether two inhibitorless RS have a common fixed point.

######  Theorem 22.

Given $\mathcal{A},\mathcal{B}\in\mathcal{RS}(\infty,0)$ with a common
background set $S$, it is NP-complete to decide whether $\mathcal{A}$ and
$\mathcal{B}$ have a common fixed point.

###### Proof.

The problem is in NP (see Table 3). In order to show NP-hardness, we reduce
sat [26] to this problem. Given a Boolean formula
$\varphi=\varphi_{1}\land\cdots\land\varphi_{m}$ in CNF over the variables
$V=\\{x_{1},\dots,x_{n}\\}$, let
$\heartsuit_{S}\coloneqq\\{\heartsuit_{i}:1\leq i\leq n\\}$ be a set of extra
entities that are not contained in $V\cup\overline{V}$. We define a RS
$\mathcal{A}$ with background set $S\coloneqq
V\cup\overline{V}\cup\heartsuit_{S}\cup\\{\spadesuit\\}$ (with
$\spadesuit\not\in V\cup\overline{V}\cup\heartsuit_{S}$ and $V,\overline{V}$
as in Definition 4) and the reactions

$\displaystyle(\textnormal{neg}(\varphi_{j})\cup\overline{\textnormal{pos}}(\varphi_{j})\cup\heartsuit_{S},\varnothing,\\{\spadesuit\\})$
for $\displaystyle 1\leq j\leq m$ (41)
$\displaystyle(\\{x_{i}\\}\cup\heartsuit_{S},\varnothing,\\{\heartsuit_{i},x_{i}\\})$
for $\displaystyle 1\leq i\leq n$ (42)
$\displaystyle(\\{\overline{x_{i}}\\}\cup\heartsuit_{S},\varnothing,\\{\heartsuit_{i},\overline{x_{i}}\\})$
for $\displaystyle 1\leq i\leq n$ (43)
$\displaystyle(\\{x_{i},\overline{x_{i}}\\}\cup\heartsuit_{S},\varnothing,\\{\spadesuit\\})$
for $\displaystyle 1\leq i\leq n$ (44)
$\displaystyle(\\{\spadesuit\\}\cup\heartsuit_{S},\varnothing,\\{\spadesuit\\}).$
(45)

Note that for all $Y\subseteq V\cup\overline{V}$, and for every
$Z_{\heartsuit}\subsetneq\heartsuit_{S}$ it holds

$\mathrm{res}_{\mathcal{A}}(Y\cup
Z_{\heartsuit})=\mathrm{res}_{\mathcal{A}}(Y\cup
Z_{\heartsuit}\cup\\{\spadesuit\\})=\varnothing=\mathrm{res}_{\mathcal{A}}(\varnothing)$
(46)

because no reaction is enabled. We thus consider states $T\subseteq S$ such
that $\heartsuit_{S}\subseteq T$. For every $Y\subseteq V\cup\overline{V}$, we
define $\heartsuit_{Y}\coloneqq\\{\heartsuit_{i}:x_{i}\in
Y\lor\overline{x_{i}}\in Y\\}\subseteq\heartsuit_{S}$. Note that
$\heartsuit_{Y}=\mathrm{res}_{\mathcal{A}}(Y\cup\heartsuit_{S})\cap\heartsuit_{S}=\mathrm{res}_{\mathcal{A}}(Y\cup\heartsuit_{S}\cup\\{\spadesuit\\})\cap\heartsuit_{S}$,
so when $\heartsuit_{Y}\subsetneq\heartsuit_{S}$, the states
$Y\cup\heartsuit_{S}$ and $Y\cup\heartsuit_{S}\cup\\{\spadesuit\\}$ reach
$\varnothing$ in two steps. In particular, if $T\neq\varnothing$ is a fixed
point then it must be of the form $T=Y\cup\heartsuit_{Y}$ or
$T=Y\cup\heartsuit_{Y}\cup\\{\spadesuit\\}$ with $Y\subseteq
V\cup\overline{V}$ and $\heartsuit_{Y}=\heartsuit_{S}$. We remark that
$\heartsuit_{Y}=\heartsuit_{S}$ means that $x_{i}\in Y$ or
$\overline{x_{i}}\in Y$ for all $1\leq i\leq n$. We divide two cases:

  1. (i)

$Y$ is not a well-formed state. Since $\heartsuit_{Y}=\heartsuit_{S}$, there
exist $x_{i},\overline{x_{i}}\in Y$, so $\spadesuit$ is generated by one of
the reactions of type (44). We obtain that
$Y\cup\heartsuit_{S}\cup\\{\spadesuit\\}$ is a fixed point reachable from
$Y\cup\heartsuit_{S}$.

  2. (ii)

$Y$ is a well-formed state. If $Y\vDash\varphi$ then no reaction of type (41)
is enabled, so $Y\cup\heartsuit_{S}$ is a fixed point (not reachable from any
other state). Also in this case, $Y\cup\heartsuit_{S}\cup\\{\spadesuit\\}$ is
a fixed point, thanks to reaction (45). On the other hand, if
$Y\nvDash\varphi$ then $Y\cup\heartsuit_{S}\cup\\{\spadesuit\\}$ is a fixed
point reachable from $Y\cup\heartsuit_{S}$.

Now, consider the RS $\mathcal{B}$ given by the following reactions:

$\displaystyle(\varnothing,\varnothing,\heartsuit_{S})$ (47)
$\displaystyle(\\{x_{i}\\},\varnothing,\\{x_{i}\\})$ for $\displaystyle 1\leq
i\leq n$ (48)
$\displaystyle(\\{\overline{x_{i}}\\},\varnothing,\\{\overline{x_{i}}\\})$ for
$\displaystyle 1\leq i\leq n.$ (49)

The fixed points of $\mathcal{B}$ are the states $Y\cup\heartsuit_{S}$ for all
$Y\subseteq V\cup\overline{V}$. We can conclude that $\mathcal{A}$ and
$\mathcal{B}$ share a fixed point exactly when there exists an assignment
satisfying $\varphi$, i.e., $\varphi$ is satisfiable. Since the mapping
$\varphi\mapsto(\mathcal{A},\mathcal{B})$ is computable in polynomial time,
the problem is NP-hard. ∎

We next show that determining whether two inhibitorless RS have a common fixed
point attractor is NP-complete. The proof is an adaptation of the proof of
Theorem 22.

######  Corollary 23.

Given $\mathcal{A},\mathcal{B}\in\mathcal{RS}(\infty,0)$ with a common
background set $S$, it is NP-complete to decide whether $\mathcal{A}$ and
$\mathcal{B}$ have a common fixed point attractor.

###### Proof.

The problem is in NP (see Table 3). Following the proof of Theorem 22, we just
need to ensure that the fixed points of $\mathcal{A}$ are attractors, so we
delete reaction (45) from the reactions of $\mathcal{A}$. In this way, when
$Y\subset V\cup\overline{V}$ and $Y\vDash\varphi$, we have that

$\mathrm{res}_{\mathcal{A}}(Y\cup\heartsuit_{S}\cup\\{\spadesuit\\})=Y\cup\heartsuit_{S}=\mathrm{res}_{\mathcal{A}}(Y\cup\heartsuit_{S}),$

thus $Y\cup\heartsuit_{S}$ is a fixed point reachable from
$Y\cup\heartsuit_{S}\cup\\{\spadesuit\\}$. We can conclude that $\mathcal{A}$
and $\mathcal{B}$ share a fixed point attractor exactly when there exists an
assignment satisfying $\varphi$, i.e., $\varphi$ is satisfiable. Since the
mapping $\varphi\mapsto(\mathcal{A},\mathcal{B})$ is computable in polynomial
time, the problem is NP-hard.∎

We now consider the problem of deciding if two RS share all their fixed points
and prove that, like in the case of reactantless systems, this problem is
coNP-complete.

######  Theorem 24.

Given $\mathcal{A},\mathcal{B}\in\mathcal{RS}(\infty,0)$ with a common
background set $S$, it is coNP-complete to decide whether $\mathcal{A}$ and
$\mathcal{B}$ share all their fixed points.

###### Proof.

The problem lies in coNP (see Table 3). In order to show coNP-completeness, we
reduce validity [26] to this problem. Given a Boolean formula
$\varphi=\varphi_{1}\lor\cdots\lor\varphi_{m}$ in DNF over the variables
$V=\\{x_{1},\dots,x_{n}\\}$, let
$\heartsuit_{S}\coloneqq\\{\heartsuit_{i}:1\leq i\leq n\\}$ be a set of extra
entities. We define a RS $\mathcal{A}$ with background set $S\coloneqq
V\cup\overline{V}\cup\heartsuit_{S}\cup\\{\heartsuit\\}$ (with
$\heartsuit\notin V\cup\overline{V}\cup\heartsuit_{S}$ and $V,\overline{V}$ as
in Definition 4) and the reactions

$\displaystyle(\overline{\textnormal{neg}}(\varphi_{j})\cup\textnormal{pos}(\varphi_{j})\cup\heartsuit_{S}\cup\\{\heartsuit\\},\varnothing,\\{\heartsuit\\})$
for $\displaystyle 1\leq j\leq m$ (50)
$\displaystyle(\\{x_{i}\\}\cup\heartsuit_{S},\varnothing,\\{\heartsuit_{i},x_{i}\\})$
for $\displaystyle 1\leq i\leq n$ (51)
$\displaystyle(\\{\overline{x_{i}}\\}\cup\heartsuit_{S},\varnothing,\\{\heartsuit_{i},\overline{x_{i}}\\})$
for $\displaystyle 1\leq i\leq n$ (52)
$\displaystyle(\\{x_{i},\overline{x_{i}}\\}\cup\heartsuit_{S},\varnothing,\\{\heartsuit\\})$
for $\displaystyle 1\leq i\leq n.$ (53)

For every $Y\subseteq V\cup\overline{V}$, we define
$\heartsuit_{Y}\coloneqq\\{\heartsuit_{i}:x_{i}\in Y\lor\overline{x_{i}}\in
Y\\}\subseteq\heartsuit_{S}$. As in the proof of Theorem 22, if
$T\neq\varnothing$ is a fixed point then it must be of the form
$T=Y\cup\heartsuit_{Y}$ or $T=Y\cup\heartsuit_{Y}\cup\\{\heartsuit\\}$ with
$\heartsuit_{Y}=\heartsuit_{S}$. We divide two cases:

  1. (i)

$Y$ is not a well-formed state. Then, since $\heartsuit_{Y}=\heartsuit_{S}$,
there exist $x_{i},\overline{x_{i}}\in Y$, so $\heartsuit$ is generated by one
of the reactions of type (53). We get that
$Y\cup\heartsuit_{Y}\cup\\{\heartsuit\\}$ is a fixed point reachable from
$Y\cup\heartsuit_{Y}$.

  2. (ii)

$Y$ is a well-formed state. Then, if $Y\vDash\varphi$, a reaction of type (50)
is enabled by $Y\cup\heartsuit_{Y}\cup\\{\heartsuit\\}$, so
$Y\cup\heartsuit_{Y}\cup\\{\heartsuit\\}$ is a fixed point (not reachable from
any other state). In this case, also $Y\cup\heartsuit_{S}$ is a fixed point
since reactions of type (50) are not enabled. On the other hand, if
$Y\nvDash\varphi$ then $Y\cup\heartsuit_{S}$ is a fixed point reachable from
$Y\cup\heartsuit_{S}\cup\\{\heartsuit\\}$.

Now, consider the RS $\mathcal{B}$ given by the following reactions:

$\displaystyle(\\{\heartsuit\\}\cup\heartsuit_{S},\varnothing,\\{\heartsuit\\})$
(54)
$\displaystyle(\\{x_{i}\\}\cup\heartsuit_{S},\varnothing,\\{\heartsuit_{i},x_{i}\\})$
for $\displaystyle 1\leq i\leq n$ (55)
$\displaystyle(\\{\overline{x_{i}}\\}\cup\heartsuit_{S},\varnothing,\\{\heartsuit_{i},\overline{x_{i}}\\})$
for $\displaystyle 1\leq i\leq n$ (56)
$\displaystyle(\\{x_{i},\overline{x_{i}}\\}\cup\heartsuit_{S},\varnothing,\\{\heartsuit\\})$
for $\displaystyle 1\leq i\leq n.$ (57)

With a similar analysis as above, for every well-formed state $Y\subseteq
V\cup\overline{V}$ the states $Y\cup\heartsuit_{S}$,
$Y\cup\heartsuit_{Y}\cup\\{\heartsuit\\}$ are fixed points (not attractors),
and for every not-well-formed state $Y\subseteq V\cup\overline{V}$ such that
$\heartsuit_{Y}=\heartsuit_{S}$ the state
$Y\cup\heartsuit_{Y}\cup\\{\heartsuit\\}$ is a fixed point reachable from
$Y\cup\heartsuit_{S}$. We can conclude that $\mathcal{A}$ and $\mathcal{B}$
share all fixed points exactly when all assignments satisfy $\varphi$, i.e.,
$\varphi$ is a tautology. Since the mapping
$\varphi\mapsto(\mathcal{A},\mathcal{B})$ is computable in polynomial time,
the problem is coNP-hard.∎

######  Corollary 25.

Given $\mathcal{A},\mathcal{B}\in\mathcal{RS}(\infty,0)$ with a common
background set $S$, it is coNP-complete to decide whether $\mathcal{A}$ and
$\mathcal{B}$ share all their fixed points that are not attractors.

###### Proof.

The problem is in coNP (see Table 3). The coNP-hardness follows from the same
construction of Theorem 24. ∎

In contrast, deciding whether two inhibitorless reaction systems share all
their fixed points that are attractors is
$\mathbf{\Pi}_{2}^{\textnormal{{P}}}$-complete.

######  Theorem 26.

Given $\mathcal{A},\mathcal{B}\in\mathcal{RS}(\infty,0)$ with a common
background set $S$, it is $\mathbf{\Pi}_{2}^{\textnormal{{P}}}$-complete to
decide if $\mathcal{A}$ and $\mathcal{B}$ share all their fixed point
attractors.

###### Proof.

The problem is in $\mathbf{\Pi}_{2}^{\textnormal{{P}}}$ (see Table 3). In
order to show $\mathbf{\Pi}_{2}^{\textnormal{{P}}}$-hardness, we reduce
$\forall\exists$sat [27] to this problem. Given a quantified Boolean formula
$(\forall V_{1})(\exists V_{2})\varphi$ over $V=\\{x_{1},\dots,x_{n}\\}$, with
$V_{1}\subseteq V$, $V_{2}=V\setminus V_{1}$ and
$\varphi=\varphi_{1}\land\cdots\land\varphi_{m}$ quantifier-free and in CNF,
let $V^{\prime}_{1}=\\{x^{\prime}:x\in V_{1}\\}$ and
$\heartsuit_{S}\coloneqq\\{\heartsuit_{i}:1\leq i\leq n\\}$ be extra sets of
entities. We define $\mathcal{A}$ a RS with background set $S\coloneqq
V\cup\overline{V}\cup V^{\prime}_{1}\cup
C\cup\heartsuit_{S}\cup\\{\clubsuit,\spadesuit\\}$ (see also Definition 4) and
the reactions

$\displaystyle(\\{x\\},\varnothing,\\{\varphi_{j}\\})$ for $\displaystyle
1\leq j\leq m\text{ and }x\in\textnormal{pos}(\varphi_{j})$ (58)
$\displaystyle(\\{\overline{x}\\},\varnothing,\\{\varphi_{j}\\})$ for
$\displaystyle 1\leq j\leq m\text{ and
}\overline{x}\in\overline{\textnormal{neg}}(\varphi_{j})$ (59)
$\displaystyle(\textnormal{neg}(\varphi_{j})\cup\overline{\textnormal{pos}}(\varphi_{j}),\varnothing,\\{\spadesuit\\})$
for $\displaystyle 1\leq j\leq m$ (60)
$\displaystyle(\\{x_{i}\\},\varnothing,\\{\heartsuit_{i}\\})$ for
$\displaystyle 1\leq i\leq n$ (61)
$\displaystyle(\\{\overline{x_{i}}\\},\varnothing,\\{\heartsuit_{i}\\})$ for
$\displaystyle 1\leq i\leq n$ (62)
$\displaystyle(\\{x_{i},\overline{x_{i}}\\},\varnothing,\\{\clubsuit\\})$ for
$\displaystyle 1\leq i\leq n$ (63)
$\displaystyle(\\{x\\},\varnothing,\\{x^{\prime}\\})$ for $\displaystyle x\in
V_{1}$ (64)
$\displaystyle(C\cup\heartsuit_{S},\varnothing,C\cup\heartsuit_{S})$ (65)
$\displaystyle(C\cup\heartsuit_{S}\cup\\{x^{\prime}\\},\varnothing,\\{x^{\prime}\\})$
for $\displaystyle x^{\prime}\in V^{\prime}_{1}$ (66)
$\displaystyle(C\cup\heartsuit_{S}\cup\\{x_{i}\\},\varnothing,\\{\clubsuit\\})$
for $\displaystyle 1\leq i\leq n$ (67)
$\displaystyle(C\cup\heartsuit_{S}\cup\\{\overline{x_{i}}\\},\varnothing,\\{\clubsuit\\})$
for $\displaystyle 1\leq i\leq n$ (68)
$\displaystyle(\\{\clubsuit\\},\varnothing,\\{\clubsuit\\})$ (69)
$\displaystyle(\\{\spadesuit\\},\varnothing,\\{\clubsuit\\}).$ (70)

We first note that for any $T\subseteq S\setminus\\{\clubsuit\\}$ we have
$\mathrm{res}_{\mathcal{A}}(T\cup\\{\clubsuit\\})=\mathrm{res}_{\mathcal{A}}(T)\cup\\{\clubsuit\\}$.
We start by determining the fixed points of $\mathcal{A}$. We notice that if
$T$ is a fixed point then it must be $T=\mathrm{res}_{\mathcal{A}}(T)\subseteq
C\cup\heartsuit_{S}\cup V_{1}^{\prime}\cup\\{\clubsuit,\spadesuit\\}$, because
this is the union of the products of all reactions. Furthermore, the only way
for $\spadesuit$ to be part of the product is through reactions (60) which use
reactants in $V\cup\overline{V}$ that are never part of a fixed point, as we
already noticed.

For the same reason, the only reactions that can give rise to a fixed point
are (65), (66), (69) and thus we deduce that all the fixed points of
$\mathcal{A}$ are $\varnothing$, $\\{\clubsuit\\}$, and those of the form
$C\cup\heartsuit_{S}\cup U\cup\\{\clubsuit\\}$ or $C\cup\heartsuit_{S}\cup U$,
with $U\subseteq V^{\prime}_{1}$. The states $\varnothing$, $\\{\clubsuit\\}$
and $C\cup\heartsuit_{S}\cup U\cup\\{\clubsuit\\}$ are all attractors, so we
now focus on understanding when a state of the form $C\cup\heartsuit_{S}\cup
U$ is a fixed point attractor for a given $U\subseteq V^{\prime}_{1}$.

Let $T\neq C\cup\heartsuit_{S}\cup U$ be a state such that
$\mathrm{res}_{\mathcal{A}}(T)=C\cup\heartsuit_{S}\cup U$. Since
$\clubsuit\notin\mathrm{res}_{\mathcal{A}}(T)$, neither (69) or (70) can be
enabled, thus $\clubsuit\notin T$ and $\spadesuit\notin T$. We obtain that $T$
is of the form

$T=T_{V}\cup T_{\overline{V}}\cup T_{V^{\prime}_{1}}\cup T_{C}\cup
T_{\heartsuit_{S}}$

where $T_{V}\coloneqq T\cap V$ and analogously for $T_{\overline{V}}$,
$T_{V^{\prime}_{1}}$, $T_{C}$ and $T_{\heartsuit_{S}}$. If we had $T_{C}=C$
and $T_{\heartsuit_{S}}=\heartsuit_{S}$, then we would also have
$T_{V}=T_{\overline{V}}=\varnothing$ as otherwise
$\clubsuit\in\mathrm{res}_{\mathcal{A}}(T)$ would be generated by at least one
of reactions of type (67) or (68). Thus, in this case, we would have
$C\cup\heartsuit_{S}\cup
U=\mathrm{res}_{\mathcal{A}}(T)=C\cup\heartsuit_{S}\cup T_{V^{\prime}_{1}}=T$,
which is a contradiction. Therefore it must hold $T_{C}\subsetneq C$ and
$T_{\heartsuit_{S}}\subsetneq\heartsuit_{S}$, and, collecting all together,
the reactions of type (65), (66), (66), (67), (68), (69) and (70) are not
enabled.

We further remark that as in the previous proofs, $T_{V}\cup T_{\overline{V}}$
must be a well-formed assignment for $\varphi$. Furthermore if $T_{V}\cup
T_{\overline{V}}\vDash\varphi$ then
$\mathrm{res}_{\mathcal{A}}(T)=C\cup\heartsuit_{S}\cup\\{x^{\prime}:x\in
T_{V}\cap V_{1}\\}$. We can also remark that
$\spadesuit\in\mathrm{res}_{\mathcal{A}}(T)$ if and only if there exists a
$\varphi_{j}\in C$ that is not satisfied by the assignment corresponding to
$T_{V}\cup T_{\overline{V}}$. We deduce that $C\cup\heartsuit_{S}\cup U$ is a
fixed point attractor if and only if there exists an assignment
$X\cup\overline{V\setminus X}$ such that $\\{x:x^{\prime}\in U\\}\subseteq X$
and $X\cup\overline{V\setminus X}\vDash\varphi$. We conclude that all fixed
points of $\mathcal{A}$ are attractors if and only $(\forall V_{1})(\exists
V_{2})\varphi$ is valid.

We now finally consider a RS $\mathcal{B}$ with background set $S$ and
reactions (65), (66), (69). All the fixed points of $\mathcal{B}$ are
attractors and coincide with the ones of $\mathcal{A}$. The mapping
$\varphi\mapsto(\mathcal{A},\mathcal{B})$ is computable in polynomial time,
hence deciding if two RS share all their fixed point attractors is
$\mathbf{\Pi}_{2}^{\textnormal{{P}}}$-hard. ∎

######  Corollary 27.

Given $\mathcal{A}\in\mathcal{RS}(\infty,0)$ it is
$\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$-complete to decide whether
$\mathcal{A}$ has a fixed point which is not an attractor.

###### Proof.

The problem is in $\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$ (see Table 3).
Consider the converse problem, i.e., deciding if all fixed points are
attractors. The $\mathbf{\Pi}_{2}^{\textnormal{{P}}}$-hardness of the latter
follows from the construction of the RS $\mathcal{A}$ in the proof of Theorem
26. Therefore our problem is
$\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$-complete. ∎

######  Corollary 28.

Given $\mathcal{A},\mathcal{B}\in\mathcal{RS}(\infty,0)$ with a common
background set $S$, it is $\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$-complete to
decide whether $\mathcal{A}$ and $\mathcal{B}$ have a common fixed point which
is not an attractor.

###### Proof.

The problem is in $\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$ (see Table 3); by
Corollary 27, when $\mathcal{A}=\mathcal{B}$ the problem is
$\mathbf{\Sigma}_{2}^{\textnormal{{P}}}$-complete. ∎

##  7 Equal Result function

In this section, we study the problem of deciding if two RS have the same
result function. This problem lies in coNP and is complete in general RS.

######  Theorem 29.

Given $\mathcal{A},\mathcal{B}\in\mathcal{RS}(\infty,\infty)$ with the same
background set $S$, it is coNP-complete to decide whether
$\mathrm{res}_{\mathcal{A}}=\mathrm{res}_{\mathcal{B}}$.

###### Proof.

The problem lies in coNP (see Table 3). In order to show coNP-completeness, we
reduce validity [26] to this problem. Given a Boolean formula
$\varphi=\varphi_{1}\lor\cdots\lor\varphi_{m}$ in DNF over the variables
$V=\\{x_{1},\dots,x_{n}\\}$, build the RS $\mathcal{A}$ consisting of the
background set $S\coloneqq V\cup\\{\heartsuit\\}$ (with $\heartsuit\notin V$,
and $\textnormal{pos}(\varphi_{r})\subseteq V$ and
$\textnormal{neg}(\varphi_{r})\subseteq V$ the set of variables that occur
non-negated and negated in $\varphi_{r}$, respectively) and the following
reactions:

$(\textnormal{pos}(\varphi_{j}),\textnormal{neg}(\varphi_{j}),\\{\heartsuit\\})\qquad\text{for
}1\leq j\leq m.$ (71)

For any state $T\subseteq S$, $T\cap V$ encodes a truth assignment of
$\varphi$. In this way, the reactions of type (71) evaluate each conjunctive
clause and produce the element $\heartsuit$ if the clause (and thus the whole
formula $\varphi$) is satisfied. Then the RS behaves as follows:

$\mathrm{res}_{\mathcal{A}}(T)=\begin{cases}\heartsuit&\text{if }T\cap
V\vDash\varphi\\\ \varnothing&\text{if }T\cap V\nvDash\varphi.\end{cases}$

Now let $\mathcal{B}$ be the constant RS defined by the reaction
$(\varnothing,\varnothing,\\{\heartsuit\\})$ alone.

By construction, $\mathrm{res}_{\mathcal{A}}=\mathrm{res}_{\mathcal{B}}$ when
all assignments satisfy $\varphi$. Since the map
$\varphi\mapsto(\mathcal{A},\mathcal{B})$ is computable in polynomial time,
deciding if $\mathrm{res}_{\mathcal{A}}=\mathrm{res}_{\mathcal{B}}$ is coNP-
hard. ∎

Since in the previous proof the RS $\mathcal{B}$ is constant, the problem of
deciding if the result function of a RS is a non-empty constant is coNP-
complete in unconstrained reaction systems. In contrast, deciding if a result
function is empty can be done in polynomial time.

######  Corollary 30.

Given $\mathcal{A}\in\mathcal{RS}(\infty,\infty)$, it is coNP-complete to
decide if $\mathrm{res}_{\mathcal{A}}$ is a non-empty constant function;
however, deciding if $\mathrm{res}_{\mathcal{A}}=\varnothing$ is in P.

###### Proof.

The first part of the statement follows directly from the proof of Theorem 29.
Note that given a RS $\mathcal{A}=(S,A)$ and a reaction
$a=(R_{a},I_{a},P_{a})\in A$, there exists a state $T\subseteq S$ that enables
$a$ if and only if $R_{a}\cap I_{a}=\varnothing$. Since
$\mathrm{res}_{\mathcal{A}}=\varnothing$ if and only if any reaction is not
enabled by all states, we just need to check that $R_{a}\cap
I_{a}\neq\varnothing$ for all $a\in A$. ∎

We now consider the same problem for inhibitorless RS.

######  Proposition 31.

Given $\mathcal{A}=(S,A),\mathcal{B}=(S,B)\in\mathcal{RS}(\infty,0)$, if

$\mathrm{res}_{\mathcal{A}}(R_{a})\subseteq\mathrm{res}_{\mathcal{B}}(R_{a})\quad\forall
a\in A,$ (72)

then $\mathrm{res}_{\mathcal{A}}(T)\subseteq\mathrm{res}_{\mathcal{B}}(T)$ for
all states $T\subseteq S$.

###### Proof.

Let $T\subseteq S$ such that $T\neq R_{a}$ for all $a\in A$. By definition we
have

$\mathrm{res}_{\mathcal{A}}(T)=\bigcup_{a\in A:R_{a}\subsetneq
T}\mathrm{res}_{a}(T)=\bigcup_{a\in A:R_{a}\subsetneq
T}\mathrm{res}_{a}(R_{a})=\bigcup_{a\in A:R_{a}\subsetneq
T}\mathrm{res}_{\mathcal{A}}(R_{a}).$

By monotonicity of $\mathrm{res}_{\mathcal{B}}$, if $R_{a}\subseteq T$ then
$\mathrm{res}_{\mathcal{B}}(R_{a})\subseteq\mathrm{res}_{\mathcal{B}}(T)$, so
using (72) we obtain

$\mathrm{res}_{\mathcal{A}}(T)\subseteq\bigcup_{a\in A:R_{a}\subsetneq
T}\mathrm{res}_{\mathcal{B}}(R_{a})\subseteq\mathrm{res}_{\mathcal{B}}(T)\,.\qed$

######  Corollary 32.

Given $\mathcal{A},\mathcal{B}\in\mathcal{RS}(\infty,0)$ with a common
background set $S$, it is in P to decide whether
$\mathrm{res}_{\mathcal{A}}=\mathrm{res}_{\mathcal{B}}$.

###### Proof.

Applying Proposition 31 twice, it is possible to verify in polynomial time
that $\mathrm{res}_{\mathcal{A}}(T)\subseteq\mathrm{res}_{\mathcal{B}}(T)$ and
$\mathrm{res}_{\mathcal{B}}(T)\subseteq\mathrm{res}_{\mathcal{A}}(T)$ for all
states $T\subseteq S$. ∎

With a proof similar to the one of Proposition 31, we obtain the following
result for reactantless RS.

######  Proposition 33.

Given $\mathcal{A}=(S,A),\mathcal{B}=(S,B)\in\mathcal{RS}(0,\infty)$, if

$\mathrm{res}_{\mathcal{A}}(S\setminus
I_{a})\subseteq\mathrm{res}_{\mathcal{B}}(S\setminus I_{a})\quad\forall a\in
A,$ (73)

then $\mathrm{res}_{\mathcal{A}}(T)\subseteq\mathrm{res}_{\mathcal{B}}(T)$ for
all states $T\subseteq S$.

###### Proof.

Let $T\subseteq S$ such that $T\neq S\setminus I_{a}$ for all $a\in A$. By
definition we have

$\mathrm{res}_{\mathcal{A}}(T)=\bigcup_{a\in A:I_{a}\cap
T=\varnothing}\mathrm{res}_{a}(T)=\bigcup_{a\in A:I_{a}\cap
T=\varnothing}\mathrm{res}_{a}(S\setminus I_{a})=\bigcup_{a\in A:I_{a}\cap
T=\varnothing}\mathrm{res}_{\mathcal{A}}(S\setminus I_{a}).$

If $I_{a}\cap T=\varnothing$ then $T\subseteq S\setminus I_{a}$ and, since
$\mathcal{B}$ is antitone, we have
$\mathrm{res}_{\mathcal{B}}(T)\supseteq\mathrm{res}_{\mathcal{B}}(S\setminus
I_{a})$. Using (73), we obtain

$\mathrm{res}_{\mathcal{A}}(T)\subseteq\bigcup_{a\in A:I_{a}\cap
T=\varnothing}\mathrm{res}_{\mathcal{B}}(S\setminus
I_{a})\subseteq\mathrm{res}_{\mathcal{B}}(T)\,.\qed$

######  Corollary 34.

Given $\mathcal{A},\mathcal{B}\in\mathcal{RS}(0,\infty)$ with a common
background set $S$, it is in P to decide whether
$\mathrm{res}_{\mathcal{A}}=\mathrm{res}_{\mathcal{B}}$.

##  8 Bijective Result Function

In this section, we study the problem of deciding if the result function of a
RS is bijective. This problem is coNP-complete for
$\mathcal{RS}(\infty,\infty)$ [22, Theorem 7]. In this section, we prove that
for inhibitorless and reactantless reaction systems, the problem is in P.

######  Proposition 35.

Given $S$ a finite set and $f:2^{S}\to 2^{S}$ monotone and bijective, then
$|f(T)|=|T|$ for all $T\subseteq S$.

###### Proof.

Fix $T\subseteq S$ and set $k\coloneqq|T|$, $n\coloneqq|S|$. Given
$T_{1},T_{2}\subseteq S$ such that $T_{1}\subsetneq T\subsetneq T_{2}$ then,
since $f$ is monotone and injective, it holds

$f(T_{1})\subsetneq f(T)\subsetneq f(T_{2}).$ (74)

We can deduce two facts from (74) and the injectivity of $f$:

  1. (i)

$f(T)$ strictly contains $2^{k}-1$ distinct subsets of $S$.

  2. (ii)

$f(T)$ is strictly contained in $2^{n-k}-1$ distinct subsets of $S$.

Now suppose towards a contradiction that $m\coloneqq|f(T)|<k$; then $f(T)$ can
strictly contain at most $2^{m}-1<2^{k}-1$ different subsets of $S$,
contradicting (i). On the other hand, if $m>k$ then $f(T)$ is strictly
contained in $2^{n-m}-1>2^{n-k}-1$ different subsets of $S$, and this
contradicts (ii). We thus conclude that $m=k$, i.e., $|f(T)|=|T|$. ∎

The first consequence of Proposition 35 is that bijective monotonic functions
are completely determined by their values on the singletons.

######  Corollary 36.

Given $S$ a finite set and $f:2^{S}\to 2^{S}$ monotone and bijective, then for
all $T\subseteq S$

$f(T)=\bigcup_{x\in T}f(\\{x\\}).$ (75)

###### Proof.

Since $f$ is injective (thus, in particular, it is injective on singletons),
we have $|\cup_{x\in T}f(\\{x\\})|=|T|$; and by Proposition 35 we have
$|\cup_{x\in T}f(\\{x\\})|=|f(T)|$. By monotonicity of $f$, $\cup_{x\in
T}f(\\{x\\})\subseteq f(T)$; therefore, since the two sets have the same
cardinality, they are equal. ∎

######  Proposition 37.

Given $f:2^{S}\to 2^{S}$ injective on singletons such that
$f(\varnothing)=\varnothing$, $|f(\\{x\\})|=1$ for all $x\in S$ and Equation
(75) holds for all $T\subseteq S$, then $f$ is monotone and injective.

###### Proof.

Monotonicity follows directly from Equation (75). To prove injectivity,
consider $T_{1}\neq T_{2}$, then there exists $x\in T_{1}$, $x\notin T_{2}$.
Since $f$ is injective on singletons, $f(\\{x\\})\neq f(\\{y\\})$ for all
$y\in T_{2}$. Then $f(\\{x\\})\in f(T_{1})$ and $f(\\{x\\})\notin f(T_{2})$,
so in particular $f(T_{1})\neq f(T_{2})$. ∎

######  Remark 38.

Given $\mathcal{A}\in\mathcal{RS}(\infty,0)$ such that
$\mathrm{res}_{\mathcal{A}}$ is injective then $\mathrm{res}_{\mathcal{A}}$ is
additive, by Proposition 37 and Corollary 36. This means that $\mathcal{A}$
can be $1$-simulated by a reaction system in $\mathcal{RS}(1,0)$ obtained
deleting the reactions of $\mathcal{A}$ with more than two entities in the
reactants.

The following sufficient and necessary conditions for a monotonic function to
be bijective follow from Propositions 35 and 37 and Corollary 36.

######  Corollary 39.

Given $\mathcal{A}=(S,A)\in\mathcal{RS}(\infty,0)$,
$\mathrm{res}_{\mathcal{A}}$ is injective if and only if the following three
conditions are satisfied:

  1. 1.

$\mathrm{res}_{\mathcal{A}}(\varnothing)=\varnothing$,
$|\mathrm{res}_{\mathcal{A}}(\\{x\\})|=1$ for all $x\in S$.

  2. 2.

$\mathrm{res}_{\mathcal{A}}$ is injective on singletons.

  3. 3.

for all $(R,\varnothing,P)\in A$, it holds
$\mathrm{res}_{\mathcal{A}}(R)=\bigcup_{x\in
R}\mathrm{res}_{\mathcal{A}}(\\{x\\})$.

###### Proof.

($\Rightarrow$) Follows directly from Proposition 35 and Corollary 36.

($\Leftarrow$) Arguing as in the proof of Proposition 31, we obtain that for
all $T\subseteq S$,

$\mathrm{res}_{\mathcal{A}}(T)=\bigcup_{a\in A:R_{a}\subseteq
T}\mathrm{res}_{\mathcal{A}}(R_{a})=\bigcup_{a\in A:R_{a}\subseteq
T}\bigcup_{x\in R_{a}}\mathrm{res}_{\mathcal{A}}(\\{x\\}).$

By Condition 2, every element $x\in T$ belongs to some reaction of the form
$(\\{x\\},\varnothing,P_{x})\in A$ with $|P_{x}|=1$, so we obtain
$\mathrm{res}_{\mathcal{A}}(T)=\bigcup_{x\in
T}\mathrm{res}_{\mathcal{A}}(\\{x\\})$. The conclusion follows from
Proposition 37. ∎

Given an inhibitorless RS, we can check the three conditions of Corollary 39
in polynomial time, obtaining the following.

######  Corollary 40.

Given $\mathcal{A}\in\mathcal{RS}(\infty,0)$, deciding whether
$\mathrm{res}_{\mathcal{A}}$ is bijective is in P.

Recall that if a function $f:2^{S}\to 2^{S}$ is antitone, then $f^{2}$ is
monotone. Due to this remark, we can decide in polynomial time if the result
function of a reactantless RS is bijective.

######  Corollary 41.

Given $\mathcal{A}\in\mathcal{RS}(0,\infty)$, deciding whether
$\mathrm{res}_{\mathcal{A}}$ is bijective is in P.

###### Proof.

Since $\mathrm{res}_{\mathcal{A}}$ is antitone,
$\mathrm{res}_{\mathcal{A}}^{2}$ is monotone. Furthermore,
$\mathrm{res}_{\mathcal{A}}$ is injective if and only if
$\mathrm{res}_{\mathcal{A}}^{2}$ is injective. By Corollary 40, we can check
in polynomial time whether $\mathrm{res}_{\mathcal{A}}^{2}$ is injective, and
since $\mathrm{res}_{\mathcal{A}}^{2}(T)$ can be computed in polynomial time
from $\mathrm{res}_{\mathcal{A}}(T)$, the statement follows. ∎

##  9 Conclusions

We have determined the computational complexity of an extensive set of
decision problems regarding the dynamical behaviour of reactantless and
inhibitorless reaction systems. This analysis contributes to providing a more
comprehensive understanding of how problem complexity varies across different
models. Our findings reveal that the simplification of models does not
uniformly reduce complexity: most of the analyzed problems retain the same
complexity as in the unconstrained model in both reactantless and
inhibitorless systems, some become simpler in both the constrained settings,
and some others are equally difficult in unconstrained and reactantless
systems but become polynomially decidable in inhibitorless systems.

We leave as an open problem to determine the computational complexity of
deciding on the existence of a fixed point attractor in an inhibitorless
reaction system. As future directions for extending this work, we also plan to
study the complexity of other problems related to the dynamics of resource-
bounded reaction systems: for instance, studying cycles and global attractors,
similar to what has been done for resource-unbounded systems [22]. Moreover,
it would be interesting to establish the computational complexity of the
problems analyzed in this paper in even more constrained classes of reaction
systems, such as the special case of inhibitorless reaction systems using only
_one_ reactant per reaction.

## References

  * [1] A. Ehrenfeucht, G. Rozenberg, Basic notions of reaction systems, in: Developments in Language Theory, 8th International Conference (DLT), Vol. 3340 of Lecture Notes in Computer Science, Springer, 2004, pp. 27–29.  doi:10.1007/978-3-540-30550-7\\_3.
  * [2] A. Ehrenfeucht, G. Rozenberg, Reaction systems, Fundam. Informaticae 75 (1-4) (2007) 263–280.
URL http://content.iospress.com/articles/fundamenta-informaticae/fi75-1-4-15

  * [3] L. Corolli, C. Maj, F. Marini, D. Besozzi, G. Mauri, An excursion in reaction systems: From computer science to biology, Theor. Comput. Sci. 454 (2012) 95–108.  doi:10.1016/j.tcs.2012.04.003.
  * [4] S. Azimi, B. Iancu, I. Petre, Reaction system models for the heat shock response, Fundam. Informaticae 131 (3-4) (2014) 299–312.  doi:10.3233/FI-2014-1016.
  * [5] R. Barbuti, P. Bove, R. Gori, D. P. Gruska, F. Levi, P. Milazzo, Encoding threshold boolean networks into reaction systems for the analysis of gene regulatory networks, Fundam. Informaticae 179 (2) (2021) 205–225.  doi:10.3233/FI-2021-2021.
  * [6] S. Ivanov, I. Petre, Controllability of reaction systems, J. Membr. Comput. 2 (4) (2020) 290–302.  doi:10.1007/s41965-020-00055-x.
  * [7] E. Formenti, L. Manzoni, A. E. Porreca, On the complexity of occurrence and convergence problems in reaction systems, Nat. Comput. 14 (1) (2015) 185–191.  doi:10.1007/s11047-014-9456-3.
  * [8] S. Azimi, C. Gratie, S. Ivanov, L. Manzoni, I. Petre, A. E. Porreca, Complexity of model checking for reaction systems, Theor. Comput. Sci. 623 (2016) 103–113.  doi:10.1016/j.tcs.2015.11.040.
  * [9] R. Barbuti, R. Gori, F. Levi, P. Milazzo, Investigating dynamic causalities in reaction systems, Theor. Comput. Sci. 623 (2016) 114–145.  doi:10.1016/j.tcs.2015.11.041.
  * [10] M. S. Nobile, A. E. Porreca, S. Spolaor, L. Manzoni, P. Cazzaniga, G. Mauri, D. Besozzi, Efficient simulation of reaction systems on graphics processing units, Fundam. Informaticae 154 (1-4) (2017) 307–321.  doi:10.3233/FI-2017-1568.
  * [11] A. Dennunzio, E. Formenti, L. Manzoni, A. E. Porreca, Complexity of the dynamics of reaction systems, Inf. Comput. 267 (2019) 96–109.  doi:10.1016/j.ic.2019.03.006.
  * [12] A. Ehrenfeucht, M. G. Main, G. Rozenberg, Functions defined by reaction systems, Int. J. Found. Comput. Sci. 22 (1) (2011) 167–178.  doi:10.1142/S0129054111007927.
  * [13] A. Dennunzio, E. Formenti, L. Manzoni, A. E. Porreca, Reachability in resource-bounded reaction systems, in: Language and Automata Theory and Applications: 10th International Conference (LATA), Springer, 2016, pp. 592–602.  doi:10.1007/978-3-319-30000-9\\_45.
  * [14] S. Azimi, Steady states of constrained reaction systems, Theor. Comput. Sci. 701 (2017) 20–26.  doi:10.1016/j.tcs.2017.03.047.
  * [15] S. Kauffman, The ensemble approach to understand genetic regulatory networks, Physica A: Statistical Mechanics and its Applications 340 (4) (2004) 733–740.  doi:10.1016/j.physa.2004.05.018.
  * [16] S. Bornholdt, Boolean network models of cellular regulation: prospects and limitations, Journal of the Royal Society Interface 5 (suppl_1) (2008) S85–S94.  doi:10.1098/rsif.2008.0132.focus.
  * [17] I. Shmulevich, E. R. Dougherty, W. Zhang, From boolean to probabilistic boolean networks as models of genetic regulatory networks, Proc. IEEE 90 (11) (2002) 1778–1792.  doi:10.1109/JPROC.2002.804686.
  * [18] W. C. Teh, J. Lim, Evolvability of reaction systems and the invisibility theorem, Theoretical Computer Science 924 (2022) 17–33.  doi:10.1016/j.tcs.2022.03.039.
  * [19] A. Ehrenfeucht, J. Kleijn, M. Koutny, G. Rozenberg, Evolving reaction systems, Theoretical Computer Science 682 (2017) 79–99.  doi:10.1016/j.tcs.2016.12.031.
  * [20] E. Formenti, L. Manzoni, A. E. Porreca, Fixed points and attractors of reaction systems, in: Language, Life, Limits: 10th Conference on Computability in Europe (CiE), Springer, 2014, pp. 194–203.  doi:10.1007/978-3-319-08019-2\\_20.
  * [21] A. Granas, J. Dugundji, Elementary fixed point theorems, in: Fixed Point Theory, Springer New York, New York, 2003, pp. 9–84.
  * [22] E. Formenti, L. Manzoni, A. E. Porreca, Cycles and global attractors of reaction systems, in: Descriptional Complexity of Formal Systems: 16th International Workshop (DCFS), Springer, 2014, pp. 114–125.  doi:10.1007/978-3-319-09704-6\\_11.
  * [23] L. Manzoni, D. Pocas, A. E. Porreca, Simple reaction systems and their classification, International Journal of Foundations of Computer Science 25 (04) (2014) 441–457.  doi:10.1142/S012905411440005X.
  * [24] R. Brijder, A. Ehrenfeucht, G. Rozenberg, Reaction systems with duration., Computation, cooperation, and life 6610 (2011) 191–202.  doi:10.1007/978-3-642-20000-7\\_16.
  * [25] N. Immerman, Descriptive Complexity, Graduate Texts in Computer Science, Springer, 1999.
  * [26] C. Papadimitriou, Computational Complexity, Theoretical computer science, Addison-Wesley, 1994.
  * [27] L. J. Stockmeyer, The polynomial-time hierarchy, Theoretical Computer Science 3 (1) (1976) 1–22.  doi:10.1016/0304-3975(76)90061-X.