${\setX}\cap \{\da,\da'\}= \emptyset$.

* $\da$ and $\da'$ belong to the set $\setX$,

* $\da$ belongs to the set $\setX$, but $\da'$ does not,

* $\da'$ belongs to the set $\setX$, but $\da$ does not,

* both $\da,\da'$ do not belong $\setX$.

* In the first case, $\da$ is
not a vertex of
and $\da'$ is not a vertex of
So, $\vec{0}=\weight{setX}({\revcut{\simpleGraph{m}{\vec{a}}}{\da}})=\weight{setX}({\revcut{\simpleGraph{m}{\vec{a}}}{ \da' }}).$ Thus,
$\weight{setX}(\simpleGraph{m+1}{\vec{a}})=\vec{0}$, as

* In the second case, $\vec{0}=\weight{setX}({\revcut{\simpleGraph{m}{\vec{a}}}{\da'}})$ and
$\weight{setX-da}({\simpleGraph{m}{\vec{a}}})=\vec{0}$ as $\size{\setX\setminus \set{\da}}<m$. Thus, $\weight{setX}(\simpleGraph{m+1}{\vec{a}})=\vec{0}$, as

* The third case is almost the same as second.

* In the fourth case,
$\weight{setX}({\revcut{\simpleGraph{m}{\vec{a}}}{\da}})=\weight{setX}({\revcut{\simpleGraph{m}{\vec{a}}}{\da'}})$, so
\weight{setX}({\revcut{\simpleGraph{m}{\vec{a}}}{\da}})-\weight{setX}({\revcut{\simpleGraph{m}{\vec{a}}}{\da'}})=\vec{0},$ as required.

Claim 2.We proceed to the proof of Point 2.1011 Let $\simpleGraph{m}{\vec{a}}=\sum_i a_i {\hypergraphG}_i$ where $a_i\in \Z$,
${\hypergraphG}_i\in \eqs{\cut{{\hypergraphG}}{\da}},$ and
additionaly $\da'\not\in \bigcup_i \support{\hypergraphG_i} \cup  \support{\hypergraphG}.$ Suppose
$\pi_i$ are bijections that are identity on $\set{\da,\da'}$ and that
equivalence of summands and $\cut{{\hypergraphG}}{\da}$ i.e. ${\hypergraphG}_i=\cut{{\hypergraphG}}{\da}\circ \pi_i.$
such that $\pi_i$ are identity on $\set{\da,\da'}$ and
${\hypergraphG}_i=\cut{{\hypergraphG}}{\da}\circ \pi_i.$
They exist as sets of vertices of $\cut{{\hypergraphG}}{\da}$ and $\hypergraphG_i$ do not contain neither $\da$ nor $\da'$.
The bijections $\pi_i$ are well defined as sets of vertices of $\cut{{\hypergraphG}}{\da}$ and $\hypergraphG_i$ do not contain neither $\da$ nor $\da'$.
Due toBecause of200 point 1Point $1$1038, we may write the following equation
\[
\simpleGraph{m+1}{\vec{a}}=\sum_i a_i
\revcut{(\cut{{\hypergraphG}}{\da}\circ \pi_i)}{\da}-a_i\revcut{(\cut{{\hypergraphG}}{\da}\circ \pi_i)}{\da'}.
\]

As1044 $\pi_i$ is
identityis the identity1043 on
$\da,\da'$ we may transform the equation, so1044.

\[
\simpleGraph{m+1}{\vec{a}}=\sum_i a_i \revcut{\cut{{\hypergraphG}}{\da}}{\da}\circ \pi_i-a_i \revcut{\cut{{\hypergraphG}}{\da}}{\da'}\circ \pi_i.
\]

To prove the second claimPoint 21011 it suffices to prove that NULLfor each $i$, it holds thatNULL

\begin{equation}\label{eq:simple graph raising}
a_i \revcut{\cut{{\hypergraphG}}{\da}}{\da}\circ \pi_i-a_i \revcut{\cut{{\hypergraphG}}{\da}}{\da'} \circ \pi_i= a_i {\hypergraphG}\circ \pi_i -a_i
{\hypergraphG}'\circ \pi_i
\end{equation}

where ${\hypergraphG}' = \swap{\da}{\da'}{\hypergraphG}$.
We simplify further

\begin{equation}\label{eq:simple graph raising1}
\revcut{\cut{{\hypergraphG}}{\da}}{\da}\circ \pi_i-\revcut{\cut{{\hypergraphG}}{\da}}{\da'} \circ \pi_i= {\hypergraphG} \circ \pi_i- {\hypergraphG}' \circ
\pi_i
\end{equation}

We prove Equation <ref> by showing equality of functions $\weight{setX}$ on both sides.

To prove Equation <ref> we have to show that for every $\setSizeK$-subset $\support{\revcut{\cut{\hypergraphG}{\da}}{\da}\circ
\pi_i}\cup
\support{\revcut{\cut{\hypergraphG}{\da}}{\da'}\circ \pi_i}  \cup \support{\hypergraphG \circ \pi_i} \cup \support{\hypergraphG'\circ \pi_i}$ (for every
the weight of that subset on both sides of Equation <ref> is the same. $\support{\revcut{\cut{\hypergraphG}{\da}}{\da}\circ
\support{\revcut{\cut{\hypergraphG}{\da}}{\da'}\circ \pi_i}  \cup \support{\hypergraphG \circ \pi_i} \cup \support{\hypergraphG'\circ \pi_i}
={\pi_i}^{-1}(\support{\hypergraphG}\cup\support{\hypergraphG'}),$ so we formalise this as a following equation.
So forFor1054,1057 any ${\setX}\subseteq \pi_i\changed{^{-1}}{}{NULL}(\support{{\hypergraphG}}\cup \support{{\hypergraphG}'})$ we prove

\begin{equation}\label{eq:simple graph raising2}
\weight{setX} \left(\revcut{\cut{{\hypergraphG}}{\da}}{\da} \circ \pi_i- \revcut{\cut{{\hypergraphG}}{\da}}{\da'}\circ \pi_i\right)= \weight{setX}
\left( {\hypergraphG} \circ \pi_i-
{\hypergraphG}' \circ \pi_i\right).
\end{equation}

We consider $4$ cases depending on whether $\da,\da'\in \setX$.

* If $\setX$ does not contain $\da$ and $\da'$ then
$\weight{setX}({\hypergraphG}\circ \pi_i)=\weight{setX}({\hypergraphG}'\circ \pi_i)$, so the right handright1059 side equalsis equal
to1060 $\vec{0}$
exactly like the left-handleft1057 side of the equality

. On the left side $\weight{setX}(\cut{\hypergraphG}{\da}\circ \pi_i) = \weight{setX}(\revcut{\cut{\hypergraphG}{\da}}{\da}\circ \pi_i)=
\weight{setX}(\revcut{\cut{\hypergraphG}{\da}}{\da'}\circ \pi_i)$ so the left side is equal to $\vec{0}$.

* If $\setX$ contains only $\da$ then $\weight{setX}(\revcut{\cut{{\hypergraphG}}{\da}}{\da}\circ \pi_i)=\weight{setX}({\hypergraphG}\circ \pi_i)$
and $\weight{setX}(\revcut{\cut{{\hypergraphG}}{\da}}{\da'}\circ \pi_i)=\vec{0}=\weight{setX}({\hypergraphG}'\circ \pi_i)$, so the equality holds.

* Similarly for only $\da'$.The case where $\setX$ contains only $\da'$ is similar.1063

* If $\setX$ contains both $\da$ and $\da'$ then
$\vec{0}=\weight{setX}(\revcut{\cut{{\hypergraphG}}{\da}}{\da}\circ \pi_i)=\weight{setX}({\hypergraphG}\circ \pi_i)=
\weight{setX}(\revcut{\cut{{\hypergraphG}}{\da}}{\da'}\circ \pi_i)=\weight{setX}({\hypergraphG}'\circ \pi_i)$. So both sides of the
equalityEquation <ref>1067 are $\vec{0}$.

Thus Thus, 177the equality <ref> holds for
every $\setX$.

[This lemma is reformulated Theorem 15 from <cit.>.]

[From <cit.>, Th 15.]
Let ${\hypergraphG}=({\setVertices\changed{}{'}{NULL}},\mu\changed{}{'}{NULL})$ be a $1$-hypergraph.
Then for any $\setX\subseteq {\setVertices\changed{}{'}{NULL}}$ and $\size{\setX}\leq 1$ there is a
$1$-hypergraph $\simpleGraph{setX}{\weight{setX}(\hypergraphG)}$, such that
$\simpleGraph{setX}{\weight{setX}(\hypergraphG)}\in \sums{\Z}{\eqs{{\hypergraphG}}}$.

We consider two cases (i) $\size{\setX}=1$ and (ii) $\size{\setX}=0$.

The first case. Let ${\setX}=\{\da\}$, $\vec{a}=\weight{da}({\hypergraphG})$, and $\da'\notin {\setVertices\changed{}{'}{NULL}}$.
We define $\simpleGraph{1}{\vec{a}} \eqdef {\hypergraphG}-\swap{\da}{\da'}{\hypergraphG}.$
For any vertex $\db \neq \da,\da'$ we have $\weight{db}(\simpleGraph{1}{\vec{a}}) = \vec{0}$. So $\simpleGraph{1}{\vec{a}}$ has two
non-isolatednonisolated107 vertices
$\{\da,\da'\}$ and satisfies all properties of a
simple$(1,\vec{a})$- NULL

The second case. Let $\weight{emptyset}({\hypergraphG})= \vec{b}$, $\da'\notin {\setVertices\changed{}{'}{NULL}}$. Further, let
$\simpleGraph{1}{\mu\changed{}{'}{NULL}(\db)} =
{\hypergraphG}-\swap{\db}{\da'}{\hypergraphG}$ and1076 for any $\db\in {\setVertices\changed{}{'}{NULL}}$.
Then we put $\simpleGraph{0}{\vec{b}}\eqdef {\hypergraphG}-\left(\sum_{\db\in {\setVertices\changed{}{'}{NULL}}} \simpleGraph{1}{\mu\changed{}{'}{NULL}(\db)}
\right)$.
Indeed, it is a hypergraph with only one non-isolatednonisolated107
vertex $\da'$ and
$\weight{da'}(\simpleGraph{0}{\vec{b}})= -\sum_{\db\in
{\setVertices\changed{}{'}{NULL}}}\weight{da'}({\simpleGraph{1}{\mu\changed{}{'}{NULL}(\db)}})=\weight{emptyset}({\hypergraphG}),$ as

Let $\setSizeK\in \N$.1081
Suppose that Theorem <ref> holds if restricted to ${\setSizeK}$-hypergraphs. Let
${\hypergraphG}=({\setVertices\changed{}{'}{NULL}},\mu\changed{}{'}{NULL})$ be a
Then for any nonempty ${\setX}\subseteq {\setVertices\changed{}{'}{NULL}}$ andsuch that1082 $0<\size{\setX}\leq \setSizeK+1$ there is a
$\setSizeK+1$-$(\setSizeK+1)$-779hypergraph $\simpleGraph{setX}{\weight{setX}({\hypergraphG})}$, such that
\sums{\Z}{\eqs{{\hypergraphG}}}$.

We show how to construct the hypergraph $\simpleGraph{setX}{\weight{setX}({\hypergraphG})}$. Let $\da\in {\setX}$.
Consider $\cut{{\hypergraphG}}{\da}$ and a set ${\setX}'={\setX}\setminus\{\da\}$. Observe,
So, due tobecause of200Because of1087 the assumption we know that there is $\simpleGraph{setX'}{\weight{setX}(\hypergraphG)}$ a
$(\size{{\setX}'}, \weight{setX}({\hypergraphG}))-\simple$

$(\size{{\setX}'}, \weight{setX}({\hypergraphG}))$-1089,1093
${\setSizeK}$-hypergraph, such  that
$\simpleGraph{setX'}{\weight{setX}({\hypergraphG})}\in \sums{\Z}{\eqs{\cut{{\hypergraphG}}{\da}}}$.
Now, due tobecause of200 Lemma <ref>,  for some $\da'\notin \setVertices\changed{}{'}{NULL}$, the
\revcut{\simpleGraph{setX'}{\weight{setX}({\hypergraphG})}}{\da}-
\revcut{\simpleGraph{setX'}{\weight{setX}({\hypergraphG})}}{\da'}$ is $(\size{\setX},
\weight{setX}({\hypergraphG}))-\simple$

\weight{setX}({\hypergraphG}))$-1089,1093
(point 1) and $\simpleGraph{setX}{\weight{setX}({\hypergraphG})}\in \sums{\Z}{\eqs{{\hypergraphG}}}$ (point 2).

Let $\setSizeK\in \N$.1081
Suppose that Theorem <ref>
holds if restricted to ${\setSizeK}$-hypergraphs. Let ${\hypergraphG}$ be a $\setSizeK+1$-$(\setSizeK+1)$-779hypergraph and
Then there is a $(0,\vec{a})-\simple$$(0,\vec{a})$-20
$\setSizeK+1$-$(\setSizeK+1)$-779hypergraph $\simpleGraph{0}{\vec{a}}$ such that $\simpleGraph{0}{\vec{a}}\in \sums{\Z}{\eqs{{\hypergraphG}}}$.

First, observe that $(0, \vec{a})$- $\setSizeK+1$-$(\setSizeK+1)$-779hypergraph$\simpleGraph{0}{\vec{a}}$1099 has to satisfy
only two properties,:1100 it has $2k+1$ vertices
and the sum of weights of
all hyperedges equals $\vec{a}$.

Thus, the lemma is a consequence of a procedure (defined below) that takes a
$\setSizeK+1$-$(\setSizeK+1)$-779hypergraph $\hypergraphF$ with $l$ vertices and
if $l>2\setSizeK+1$ then it returns a
$\setSizeK+1$-$(\setSizeK+1)$-779hypergraph $\hypergraphF'$ such
that $\weight{emptyset} ({\hypergraphF})=\weight{emptyset}({\hypergraphF'})$, $\size{\support{\hypergraphF'}}<l$, and
${\hypergraphF}'\in \sums{\Z}{\eqs{\hypergraphF}}$.

The procedure applied many times starting from ${\hypergraphG}$ produces the required   hypergraph.

We start from a hypergraph $\hypergraphG$.
We apply the procedure until we produce a hypergraph with no more than than $2\setSizeK+1$ vertices. It is the required  hypergraph.
We are guaranteed to finish, as with each application the number of vertices decreases. Moreover, each application of the procedure does not change
$\weight{emptyset}$, so
we know that $\weight{emptyset}$ of the produced graph is equal to $\vec{a}$, as required.

The procedure. Let $\hypergraphF=(\setVertices,\mu)$.NULL Suppose $\da\in {\setVertices}$We pick any $\da$ in
Our goal is to construct a $\setSizeK+1$-$(\setSizeK+1)$-779hypergraph $\hypergraphF'$ such that
$\hypergraphF'\in \sums{\Z}{\eqs{\hypergraphF}}$NULL, $\support{\hypergraphF'}\subseteq \support{\hypergraphF}\setminus \{\da\}$
and $\weight{emptyset}(\hypergraphF')=\weight{emptyset}(\hypergraphF)$.1110
As the first step, we construct a
$\setSizeK+1$-$(\setSizeK+1)$-779hypergraph $\hypergraphK\in \sums{\Z}{\eqs{\hypergraphF}}$$\hypergraphK$1131 such that

* $\hypergraphK\in \sums{\Z}{\eqs{\hypergraphF}}$1131

* $\weight{emptyset}({\hypergraphK})=\vec{0}$.

* For every $\setX$, a set of vertices containing $\da$,
we have that $\weight{setX}(\hypergraphF)=\weight{setX}({\hypergraphK})$.

* $\support{{\hypergraphK}} \subseteq \support{\hypergraphF}$.

Then, $\hypergraphF'=\hypergraphF-{\hypergraphK}$.
The first property guaranties that $\hypergraphF'\in \sums{\Z}{\eqs{\{\hypergraphF\}}}$.1113
Because of the second property $\weight{emptyset}(\hypergraphF')=\weight{emptyset}(\hypergraphF)-\vec{0}=\weight{emptyset}(\hypergraphF)$.1113
The secondthird1131 property is responsible for deleting all hyperedges containing $\da$ and the thirdfourth1131 property for
not adding any new vertex.

We define ${\hypergraphK}$ as follows.
Let $\setS$ be a simple family for $\cut{\hypergraphF}{\da}$.
By,By1115 $\hat{\setS}$ we denote a setthe set1115 of all ${\setSizeK}$-hypergraphs supported by
$\changed{{\setVertices}}{\support{\hypergraphF}}{NULL}\setminus\{\da\}$ and$\hypergraphS$ such that
$\support{\hypergraphS}=\changed{{\setVertices}}{\support{\hypergraphF}}{NULL}\setminus\{\da\}$ and 759
equivalent to elements of $\setS$$\hypergraphS\in \eqs{\setS}$1116.
Due toBecause of200 Theorem <ref> we know
that $\cut{\hypergraphF}{\da}\in \sums{\changed{Z}{\Z}{1117}}{\eqs{\setS}}$ supportedis supported1117
by $\changed{{\setVertices}}{\support{\hypergraphF}}{NULL}\setminus\{\da\}$, i.e. i.e.22

\begin{equation}
\cut{\hypergraphF}{\da}=\sum_i a_i \simpleGraph{any}{}_i \text{ where } a_i \in \Z \text{ and }\simpleGraph{any}{}_i\in \hat\setS.
\end{equation}

\begin{equation}\label{eq:F description}
\changed{\text{Thus, }}{}{1121}\revcut{\cut{\hypergraphF}{\da}}{\da}=\sum_i a_i \revcut{\simpleGraph{any}{}_i}{\da}.
\end{equation}

We define ${\hypergraphK}$ as

\begin{equation}\label{eq:Y description}
\begin{split}
{\hypergraphK} \eqdef \revcut{\cut{\hypergraphF}{\da}}{\da}-\sum_i a_i \revcut{\simpleGraph{any}{}_i}{{\da}_i'}=\sum_i a_i
\revcut{\simpleGraph{any}{}_i}{{\da}_i'})\\
\changed{\text{ where each }{\da}_i'\in \changed{{\setVertices}}{\support{\hypergraphF}}{NULL}\setminus (\support{\simpleGraph{any}{}_i}\cup\{\da\}).}{}{1128}
\end{split}
\end{equation}

where each ${\da}_i'$ is any vertex in the set $\changed{{\setVertices}}{\support{\hypergraphF}}{NULL}\setminus
Observe, that $\size{\support{\simpleGraph{any}{}_i} \cup \{\da\}} \leq 2\setSizeK + 1< \size{\changed{{\setVertices}}{\support{\hypergraphF}}{NULL}}$ as
$\size{\changed{{\setVertices}}{\support{\hypergraphF}}{NULL}}>2\setSizeK+1$, so $\da_i'$ can be always picked.

${\hypergraphK}$ satisfies the required properties:

* ${\hypergraphK}\in \sums{\Z}{\eqs{\hypergraphF}}$. It is sufficient to show that
\sums{\Z}{\eqs{\hypergraphF}}$.
Due toBecause of200
the assumption that Theorem <ref>
holds for ${\setSizeK}$-hypergraphs we know that $\simpleGraph{any}{}_i\in \sums{\Z}{\eqs{\cut{\hypergraphF}{\da}}}$. If we combine this
with Lemma <ref> (point 2) then we get that each hypergraph
$(\revcut{\simpleGraph{any}{}_i}{\da}-\revcut{\simpleGraph{any}{}_i}{{\da}_i'})\in \sums{\Z}{\eqs{\hypergraphF}}$.

$(\revcut{\simpleGraph{any}{}_i}{\da}-\revcut{\simpleGraph{any}{}_i}{{\da}_i'})$ is in $\sums{\Z}{\eqs{\hypergraphF}}$.

* $\weight{emptyset}({\hypergraphK})=\vec{0}$. Due toBecause of200 Lemma <ref> (point 1) we know that
$\revcut{\simpleGraph{any}{}_i}{\da}-\revcut{\simpleGraph{any}{}_i}{{\da}_i'}$ is
an element of a simple family for $\hypergraphF$ and it is $(l,\cdot)-\simple$$(l,\cdot)$-20 for $l>0$. Thus,
$\weight{emptyset}({\revcut{\simpleGraph{any}{}_i}{\da}-\revcut{\simpleGraph{any}{}_i}{{\da}_i'}})=\vec{0}$ and $\weight{emptyset}({\hypergraphK})=\vec{0}$ as
${\hypergraphK}$ is a sum

* $\weight{setX}({\hypergraphK})=\weight{setX}(\hypergraphF)$ for any $\setX$ such that $\da\in {\setX}$. Indeed,

\[
\weight{setX}({\hypergraphK})=\sum_i \weight{setX}({\revcut{\simpleGraph{any}{}_i}{\da}})-\weight{setX}({\revcut{\simpleGraph{any}{}_i}{{\da}_i'}}) \ \text{
(\changed{}{by\ }{1143,1148}Equation~\ref{eq:Y
\]

each $\revcut{\simpleGraph{any}{}_i}{{\da}_i'}$ does not contain $\da$ thus

\[
\weight{setX}({\hypergraphK})=\sum_i
\weight{setX}(\revcut{\simpleGraph{any}{}_i}{\da})\changed{)}{}{1148}=\weight{setX}({\revcut{\cut{\hypergraphF}{\da}}{\da}}) \ \text{
(\changed{}{by\ }{1143,1148}Equation~\ref{eq:F description}).}
\]

But, according to Definition <ref> (of the $\cut{\cdot}{\da}$ operation) and Lemma <ref> we know that
for any set of vertices ${\setY}\subseteq \changed{{\setVertices}}{\support{\hypergraphF}}{NULL}\setminus\{\da\}$:

\begin{equation}\label{eq:remove v add v}
\weight{Ycup{da}}(\hypergraphF)=\weight{setY}({\cut{\hypergraphF}{\da}})=\weight{Ycup{da}}(\revcut{\cut{\hypergraphF}{\da}}{\da}).
\end{equation}

Thus Thus, 177for ${\setX}={\setY}\cup\{\da\}$ we get $\weight{setX}({\hypergraphK})=\weight{setX}(\hypergraphF)$.

* $\support{{\hypergraphK}}\subseteq \changed{{\setVertices}}{\support{\hypergraphF}}{NULL}$. Indeed, for every $\simpleGraph{any}{}_i$ holdit
holds that451
$\support{\revcut{\simpleGraph{any}{}_i}{\da}}\subseteq \changed{{\setVertices}}{\support{\hypergraphF}}{NULL}$ and
$\support{\revcut{\simpleGraph{any}{}_i}{{\da}_i}}\subseteq \changed{{\setVertices}}{\support{\hypergraphF}}{NULL}$.

The proof goes viais by1158 induction on ${\setSizeK}$. The base for the induction is given by Lemma <ref>.
The induction step is given by Lemmas <ref> and <ref>.

§ THE PROOF OF THEOREM <REF> ITSELF.

Having proven theoremsTheoremsNULL <ref> and <ref> are proven, so now,NULL the proof
of Theorem <ref> is simple.
Let us recall its statement.

Theorem <ref>
The following conditions are equivalent,
for a finite set ${\setHypergraphsH}$ of hypergraphs and a hypergraph $\hypergraphH$, all of the same arity and dimension:

* $\hypergraphH$ is a $\Z$-sum of $\eqs{{\setHypergraphsH}}$;

* $\hypergraphH$ is locally a $\Z$-sum of ${\setHypergraphsH}$.

From the left to the right.From Point $1$ to Point $2$.1163
Observe that $\weight{setX}$ is a homomorphism, for any set $\setX$.
Thus Thus, 177if1165 ${\hypergraphH}\in \sums{\Z}{\eqs{{\setHypergraphsH}}}$ i.e.
${\hypergraphH}=\sum_i a_i {\hypergraphG}_i$ where $a_i\in \Z$ and ${\hypergraphG}_i\in\eqs{{\setHypergraphsH}},$
thenthus1165 $\weight{setX}({\hypergraphH})=\sum_i a_i \weight{setX}({\hypergraphG}_i)$, for any set ${\setX}\in {\setVertices}$.
The above holds for any set ${\setX}\subseteq {\setVertices}$ thus ${\hypergraphH}$ is locally a $\Z$ sum$\Z$-sum1166 of ${\setHypergraphsH}$.

From the right to the left.From Point $2$ to Point $1$.1163 If ${\hypergraphH}$ is locally a $\Z$ sum of ${\setHypergraphsH}$ then for any set
${\setX}\subseteq {\setVertices}$ there is a
${\setSizeK}$-hypergraph ${\hypergraphG}_{\setX}$ such
$\weight{setX}({\hypergraphH})=\weight{setX}({{\hypergraphG}_{\setX}})$ and ${\hypergraphG}_{\setX}\in \sums{\Z}{\eqs{{\setHypergraphsH}}}.$
Due toBecause of200
Theorem <ref> we conclude that there is a family simple for ${\hypergraphH}$
${\{\hypergraphH\}}$NULL such that its elements are in
Now,NULL we can apply Theorem <ref> together with Lemma <ref> and conclude that ${\hypergraphH}\in
\sums{\Z}{\eqs{{\setHypergraphsH}}}$.

§ PROOF OF THEOREM <REF>.

Before we prove the theorem, let us recall its statement.

Theorem <ref>
For every fixed arity ${\setSizeK}\in \N$, the $\N$-solvability problem is in $\NETIME.$

We prove Theorem <ref> by showing that in $\NETIME$ it is possible to reduce $\N$-solvability to $\Z$-solvability.
The produced instance of $\Z$-solvability is of exponential size, and can be solved in
$\ETIME$ due tobecause of200  Theorem <ref>.

Before we start, we need to recall some facts about solution of systems of linear equations.

§ HYBRID LINEAR SETS.

A set of vectors is called hybrid linear if it is the smallest set that
includes a finite set $\setB$, called a base, and that is closed under the addition of elements
from a finite set $\setP$, called periods.

Let $M$ be a $\dimension\times m$ -matrix$\dimension\times m$-matrix1182 with integer entries and $\vec{y}\in \ktuple{\dimension}{\Z}$.
The set of nonnegative integer solutions of linear equations

\[
M \cdot \vec{x}=\vec{y}
\]

is a hybrid linear set.
The base $\setB$ and periods $\setP$ are as follows:

* Base: it is the set of minimal, in the pointwise sense, solutions of1186
$M\cdot \vec{x}=\vec{y}.$

* Periods: is the set of minimal nontrivial solutions of

\begin{equation}\label{eq:Pottier1}
M\cdot \vec{x}=\vec{0}.
\end{equation}

In the paper <cit.>,1190 Pottier provides bounds on the norms of
$\setB$ and $\setP$. We present these bounds next.1190

For a vector $\vec{v}\in \ktuple{m}{\Z} $ we introduce two norms: the infinity norm $\inorm{\vec{v}}$ and
the norm one $\norm{\vec{v}}{1}$, defined as follows:

* $\inorm{\vec{v}}\eqdef max (\setof{\abs{\vec{v}[i]}}{ \text{ for }1\leq i \leq m})$,
$\inorm{\vec{v}}\eqdef max \setof{\abs{\vec{v}[i]}}{ \text{ for }1\leq i \leq m}$.1193

* $\norm{\vec{v}}{1}\eqdef \sum_{i=1}^m \abs{\vec{v}[i]}$.

Let $\setU$ be a finite family of data vectors. We extend definitions of norms to families of data vectors.1196
Let $\norm{{\changed{\setHypergraphsH}{\setU}{1196}}}{\infty}\eqdef max(\setof{\inorm{\changed{}{\vec{v}}}}{ \changed{\vec{h}}{\vec{v}}{1196}\in
$\norm{{\changed{\setHypergraphsH}{\setU}{1196}}}{\infty}\eqdef max\setof{\inorm{\changed{\vec{h}}{\vec{v}}{1196}}}{ \changed{\vec{h}}{\vec{v}}{1196}\in

$\norm{{\changed{\setHypergraphsH}{\setU}{1196}}}{1,\infty}\eqdef max(\setof{\norm{\changed{\vec{h}}{\vec{v}}{1196}}{1}}{
\changed{\vec{h}}{\vec{v}}{1196}\in {\changed{\setHypergraphsH}{\setU}{1196}}})$

$\norm{{\changed{\setHypergraphsH}{\setU}{1196}}}{1,\infty}\eqdef max\setof{\norm{\changed{\vec{h}}{\vec{v}}{1196}}{1}}{ \changed{\vec{h}}{\vec{v}}{1196}\in

Also, for a $d\times m$-matrix $M$ we introduce
$\norm{M}{1,\infty}\eqdef \norm{\setM}{1,\infty}$ where $\setM$ is the set of columns of the matrix $M$.

Let $ M \cdot \vec{x} = \vec{y}$ be a system of linear equations such that $M$ is a $d\times m$-matrix.
Then the set of solutions in $\ktuple{m}{\N}$ is the hybrid linear set and is 1200described by
the base $\setB$ and the set of periods $\setP$ such that:

* $\setB,\setP\subset \ktuple{m}{\N}$,

* $\size{\setP}\leq d\cdot m$

* $\inorm{\setB}, \inorm{\setP}\leq (\norm{M}{1,\infty}+\inorm{\vec{y}}+2)^{d+m}.$

Let $\setU$ be a family of vectors.1205 A vector $\vec{x}\in \setU$ is reversible in a family of vectors $\setU$ if $-\vec{x}\in
\sums{\N}{\setU}$.
Vectors that are not reversible we callWe call vectors that are not reversible237 non-reversiblenonreversible107.

Thus Thus, 177from Equation <ref> and Lemma <ref> we conclude.:1207

Let $\setU_1$ and $\setU_2$ be two finite
sets of vectors in $\ktuple{\dimension}{\Z}$
such that every vector in $\setU_2$ is non-reversiblenonreversible107 in $\setU= \setU_1\cup\setU_2$.
Suppose $\vec{y}\in \sums{\N}{\setU}$. For any solution:1218

\begin{equation}\label{eq:reversability}
\vec{y}=\sum_{\vec{v}\in\setU_1}
\cdot \vec{v}+ \sum_{\vec{w}\in\setU_2} b_{\vec{w}} \cdot \vec{w}
\end{equation}

where $a_{\vec{v}}, b_{\vec{w}}\in \N$.
Then, it holds thatNULL

\[
\sum_{\vec{w}\in\setU_2} b_{\vec{w}}\leq
\size{\setU_2}\cdot \
\setU}}
\]

i.e. $\sum_{\vec{w}\in\setU_2} b_{\vec{w}}$1217 is bounded exponentially.

The set of solutions of Equation <ref> is hybrid linear, and given by some $\setB,\setP \subset \ktuple{\size{\setU_1\cup
Every period is a solution of the equation

\begin{equation}\label{eq:lemma5}
\vec{0}=\sum_{\vec{v}\in\setU_1}
\cdot \vec{v}+ \sum_{\vec{w}\in\setU_2} b'_{\vec{w}} \cdot \vec{w}.
\end{equation}

From the definition of reversibility we get that in any solution of Equation <ref> all
$b'_{\vec{w}}$ are equal to $0$.
Thus Thus, 177in every solution of
the Equation <ref>Equation <ref>,1124
the sum $\sum_{\vec{w}\in\setU_2} b_{\vec{w}}$
is bounded by $\size{\setU_2}\cdot \inorm{\setB}\leq \size{\setU_2}\cdot \
\setU}}$, where the last inequality is given by Lemma <ref>.

§ PROOF OF THEOREM <REF>.
THE MAIN PART OF THE PROOF OF THEOREM <REF>.NULL

[place/.style=circle,draw=!50,fill=!20,thick,inner sep=0pt,minimum size=4mm,
stplace/.style=rectangle,draw=!20,fill=!20,thick,inner sep=0pt,minimum size=4mm
[]		(P1) 	at (0,0)	$\vec{v}\in \sums {\N}{\perm{\setInput}}$?;
[] 	(P2)	at (8.5,0)	$h(\vec{v})\in \sums {\N}{h(\perm{\setInput}})$?;

[] 	(E1)	at (0,-3)	5cm
$\vec{v}=\sum_{\vec{v'}} a_{\vec{v'}} \vec{v'} + \sum_{\vec{w}} b_{\vec{w}} \vec{w}  $ where

$a_{\vec{v'}}\in \N, b_{\vec{w}} \in \N$

$\vec{v'}$ are data vectors reversible in $\perm{\setInput}$

$\vec{w}$ are data vectors non-reversiblenonreversible107 in $\perm{\setInput}$

[] 	(E2)	at (8.5,-3) 	6cm
$h(\vec{v})=\sum_{\vec{v'}} a_{\vec{v'}} h(\vec{v'}) + \sum_{\vec{w}} b_{\vec{w}} h(\vec{w}) $
$a_{\vec{v'}}\in \N, b_{\vec{w}} \in \N$

$h(\vec{v'})$ are data vectors reversible in $h(\perm{\setInput})$

$h(\vec{w})$ are data vectors non-reversiblenonreversible107 in $h(\perm{\setInput})$

[] 	(B1)at (0,-6)	3cm
$\sum_{\vec{w}} b_{\vec{w}}$ is bounded

[]		(B2)	at (8.5,-6) 	Lemma <ref>: exponential bound on $\sum_{\vec{w}} b_{\vec{w}}$;

[->] (P1) to node [above] $h$ (P2) ;
[-] (P1) to node [right] a solution (E1);
[->] (E1) to node [above, near end] 3cm$h$ preserves
reversibility   (E2) ;

[-] (P2) to node [ right]a solution (E2);
[-] (E2) to node [right] the bound (B2);
[->] (B2) to node [above] transfer back (B1) ;

The diagram of the proof of Theorem <ref>.

The idea of this reduction is as follows. We use $\setInput$ for a finite family of data vectors in
$\kset{\setSizeK}{\setD}\xrightarrow{}\ktuple{\dimension}{\Z}$ and $\vec{v}$ for a target vector.
Similarly to Definition <ref>
reversibility can be defined for data vectors. Namely, a data vector $\vec{y}$ is reversible in
a set of data vectors $\setInput$ if $-\vec{y}\in \sums{\N}{\perm{\setInput}}$.

The schema of the proof may be trackedThe schema of the proof may be followed1248 on the diagram in
Figure<ref>Figure <ref>1248.
Next, we define a homomorphism from data vectors $\kset{\setSizeK}{\setD} \rightarrow \ktuple{\dimension}{\Z}$ to vectors in $\ktuple{\dimension}{\Z}$.
The homomorphism is defined in such a way that it has  an additional property, namely,a property that1250 for every data vector $\vec{y}\in
\setInput$ its image
is reversible in the image of the set $\setInput$it holds that $h(\vec{y})$ is reversible in $h(\setInput)$1251
if,325 and only if,325 $\vec{y}$ is reversible in $\setInput$.
Now, the given instance of 1252$\N$-solvability problem for data vectors
$\kset{\setSizeK}{\setD}\xrightarrow{} \ktuple{\dimension}{\Z}$
(called the first problem) is transformed, via the homomorphism,
to the $\N$-solvability for vectors in $\ktuple{\dimension}{\Z}$, i.e. i.e.22 system of linear equations (called the second problem).
The homomorphic image of any solution to the first problem is also a solution ofto1255 the second problem.
Due toBecause of200 Lemma <ref>,
there is a bound on the usagenumber of appearances1256,1258 of non-reversiblenonreversible107 vectors in any solution
ofto1255 the second problem.
This bound can be then transferred back through the homomorphism. This provides us with the bound
on the usagenumber of appearances1256,1258 of non-reversiblenonreversible107 data vectors in any solution ofto1255
the first problem.
With the bound, we can guess the non-reversiblenonreversible107 part of the solution forto1255 the first problem.
What remains is to verify that our guess is correct.
To do this we have to show that the target minus the guessed non-reversiblenonreversible107 part
can be expressed using the reversible data vectors.
But this is exactly $\Z$-solvability.
Indeed, if data vectors can be reversed then we can subtract them freely.

Let $\vec{y}\colon \kset{\setSizeK}{\setD}\xrightarrow{} \ktuple{\dimension}{\Z}$ be a data vector. The  1264data projection of $\vec{y}$
is defined as
\eqdef \sum_{x\in \kset{\setSizeK}{\setD}} \vec{y}(x)$. It is well definedwell-defined1266 as $\vec{y}$ is almost everywhere equal to
For a set of data vectors $\setInput$ we define
$\Proj(\setInput)\eqdef\bigcup_{\vec{y}\in \setInput}\{\Proj(\vec{y})\}$

$\Proj(\setInput)\eqdef\setof{\Proj(\vec{y})}{\vec{y}\in \setInput}$

to be the data projection of $\setInput$. 1268[Data projection $\Proj$ is the same thing as
$\weight{emptyset}({\placeHolder})$ but in the hypergraphs domainhypergraph domain1271.
Data projection $\Proj$ is equal to a transformation that
takes a data vector and transforms it into a hypergraph (the transformation described in Section <ref>) composed with

A data projection is a homomorphism from the group of data vectors with addition to $\ktuple{\dimension}{\Z}$.

For a data vector $\vec{y}$$\vec{y}\in \kset{\setSizeK}{\setD}\to{}{\ktuple{\dimension}{\Z}}$NULL its support denoted
$\support{\vec{y}}\subset \setD$ is the set $\setof{\da}{\changed{\exists_{x\in \kset{\setSizeK}{\setD}}}{\exists {x\in \kset{\setSizeK}{\setD}}}{1274} \text{
that }\da \in x \text{ and }\vec{y}(x)\neq
\vec{0}}$. We say that the vector $\vec{y}$ is supported by a set $\setSupport\subset\setD$ if $\support{\vec{y}}\subseteq \setSupport$. The definition may
be lifted to the setsets $\setInput$1275 of data vectors $\support{\setInput}\eqdef \bigcup_{\vec{y}\in\setInput} \support{\vec{y}}.$

In the following definitions and lemmas we use notation introduced in the definition of the $\Numbers$-solvability problem (Section <ref>), so $\vec{v}$ is a single data vector and
$\setInput$ is a finite set of data vectors.1278

Let $\setSupport\eqdef \support{\setInput}\cup \support{\vec{v}}$ (as in the formulation of the $\N$-solvability problem)1278.
By $\Pi$ we denote athe1279 set of all data permutations that are identity outside of $\setSupport$ (all permutations of $\setSupport$)$\pi$ such that for any $\da\not\in\setSupport$ we have $\pi(\da)=\da$1279.
For a data vector $\vec{y}\in \setInput\cup\{\vec{v}\}$ we define the
smoothing operator, $\smooth{\vec{y}}\eqdef \sum_{\pi\in \Pi} \vec{y}\circ \pi$.

Suppose $\vec{v}$ is a data vector $\setD\to{}\Z^{2}$ as follows: $\vec{\da}=[1,2], \vec{\db}=[1,3],$ and $\vec{\dc}=[0,0]$ for any $\dc\in \setD
\setminus\{\da,\db\}$. Let $\setInput=\{\vec{v}\}$. Then $\setSupport=\{\da,\db\}$ and $\smooth{\vec{v}}(\da)=\smooth{\vec{v}}(\db)=[2,5]$
and $\smooth{\vec{v}}(\dc)=[0,0]$ for any $\dc\in \setD\setminus\{\da,\db\}$.

Let $\setSizeK, \setSupport$ be as defined above.
There is thea1283 constant $c$ depending on ${\setSizeK}$ and $\size{\setSupport}$, such that for any
$x\in \kset{\setSizeK}{\setSupport}$ and any data vector $\vec{y}\in \setInput\cup\{\vec{v}\}$ the
$\smooth{\vec{y}}(x)=\Proj(\vec{y})\cdot c$ holds.

It holdsNULL Due tobecause of200 symmetry of the formula defining the smooth operator1286.
We do not need the explicit formulaWe do not need to calculate the value of $c$1286.

$\vec{y}\in \setInput$ is reversible in
$\perm{\setInput}$ if,325 and only if,325 $\Proj(\vec{y})$ is reversible in $\Proj(\setInput)$.

Trivial as $\Proj$ is a homomorphism.

Let $\setSupport$ and $\Pi$ be as in Definition <ref>.
We list elements of $\setInput=\{\vec{v_1}\ldots \vec{v_m}\}$.
By $M$ we denote the $1\times m$-matrix with entries in $\ktuple{\dimension}{\Z}$
such that $X[1][j]=\Proj(\vec{w})$$M[1][j]=\Proj(\vec{v_j})$1290.

From the assumptions we know that there is a
vector $\vec{x}\in \ktuple{m}{\N}$ such that

\begin{align}\label{eq:pattern1}
M\cdot \vec{x}= -\Proj(\vec{y}).
\end{align}

Let $c$ be the constant from Lemma <ref>.
We multiply both sides of Equation <ref> by $c$ getting

\begin{align*}%\label{eq:pattern2}
c\cdot M\cdot \vec{x}= -c\cdot \Proj(\vec{y}).
\end{align*}

But from this and Lemma <ref> we conclude that for any $z\in \kset{\setSizeK}{\setSupport}$

\begin{align*}%\label{eq:pattern3}
\left( \sum_{\vec{v_i}\in{\setInput}}(\smooth{\vec{v_i}}\cdot \vec{x}[i]) \right)(z) = -\smooth{\vec{y}}(z)
\end{align*}

and what followsand it follows that1301

\begin{align*}\label{eq:pattern3}
\changed{\left(\sum_{\vec{v_i}\in{\setInput}} (\smooth{\vec{v_i}}\cdot \vec{x}[i]) \right) = -\smooth{\vec{y}}.}
{\sum_{\vec{v_i}\in{\setInput}} (\smooth{\vec{v_i}}\cdot \vec{x}[i])  = -\smooth{\vec{y}}.
\end{align*}

Using the definition of smoothing we rewrite further

\begin{align*}%\label{eq:pattern4}
\sum_{\vec{v_i}\in\setInput}(\smooth{\vec{v_i}}\cdot \vec{x}[i]) +
\sum_{\pi\in \Pi\setminus\{identity\}} \vec{y}\circ \pi
= -\vec{y}.
\end{align*}

As $\vec{y}\in \setInput$ we see that we expressed $-\vec{y}$ as a sum of elements in

Non-reversible in $\perm{\setInput}$ elements of $\setInput$ can be identified in $\PTIME$ (independently from $\dimension$).

For a given vector $\vec{y}$ in $\setInput$, in $\PTIME$ we can answer if $\vec{y}$ is nonreversible in $\perm{\setInput}$. The complexity depends
polynomially from $\setSizeK$ and $\dimension$.
1310, 1311

Let $\vec{y}\in \setInput$.. The data vector1312 $\vec{y}$ is reversible in $\perm{\setInput}$ if,325 and only if,325
there is $l\in \N$ such that $-l\cdot \Proj({\vec{y}})\in
\sums{\N}{\Proj({\setInput})}$. Indeed, it is sufficient to add $(l-1) \Proj({\vec{y}})$. Thus Thus, 177the question about reversibility is
equivalent to the question
ifof whether1314 $\Proj({\vec{y}})\in \sums{\Q_+}{\Proj({\setInput})}$, where $\Q_+$ stands for nonnegative rationals. The last question is known as the linear programming
problem and is known to be solvable in $\PTIME$ <cit.>.

Let $\setInput_1$ and $\setInput_2$ form the partition of the set $\setInput$ such that $\setInput_1$ is the set of data vectors
reversible in $\perm{\setInput}$ and $\setInput_2$ is the set of data vectors non-reversiblenonreversible1319 in $\perm{\setInput}$.
Suppose $\vec{v}$ can be expressed as a sum

\begin{equation}\label{eq:lembound}
\vec{v}=\left(\sum_{\vec{v_i}\in \perm{\setInput_1}} a_i \vec{v_i}
\right)+\left(\sum_{\vec{w}\in \perm{\setInput_2}}b_{\vec{w}} \vec{w}
\right) \text{ where } a_i,b_{\vec{w}}\in \N.
\end{equation}

\begin{equation}\label{eq:lembound}
\vec{v}=\left(\sum_{\vec{y}\in \perm{\setInput_1}} a_{\vec{y}} \vec{y}
\right)+\left(\sum_{\vec{w}\in \perm{\setInput_2}}b_{\vec{w}}\vec{w}
\right) \text{ where } a_{\vec{y}},b_{\vec{w}}\in \N.
\end{equation}

Then the sum $\sum_{\vec{w}\in \perm{\setInput_2}}b_{\vec{w}}$ is bounded exponentially,
$\sum_{\vec{w}\in\perm{\setInput_2}} b_{\vec{w}}\leq
\size{\Proj(\setInput_2)}\cdot \
\setInput}}.$

The proof is based on the bound for a solution in $\N$ of a system of linear equations (Lemma <ref>). By $\Auth$ we denote the set of data
permutations (bijections $\setD \xrightarrow{} \setD$).
Indeed weWe1328 can apply the homomorphism $\Proj$ to both sides of Equation <ref> and get

\begin{align*}
\Proj(\vec{v})=\Proj\left(\sum_{\vec{y}\in \perm{\setInput_1}} a_{\vec{y}}\vec{y}
\right)+\Proj\left(\sum_{\vec{w}\in \perm{\setInput_2}}b_{\vec{w}}\vec{w}
\right)
\end{align*}

and further

\begin{align}\label{eq:projection}
\Proj(\vec{v})=\left(\sum_{\vec{y}\in \perm{\setInput_1}}a_{\vec{y}} \Proj(\vec{y})
\right)+\left(\sum_{\vec{w}\in \perm{\setInput_2}}b_{\vec{w}} \Proj(\vec{w})
\right)
\end{align}

\begin{align*}
\Proj(\vec{v})=\left(\sum_{\vec{y}\in \setInput_1} \Proj(\vec{y}) \sum_{\pi\in \Auth} a_{\vec{y},\pi}
\right)+\left(\sum_{\vec{w}\in \setInput_2} \Proj(\vec{w}) \sum_{\pi\in \Auth} b_{\vec{w},\pi}
\right)
\end{align*}

Where $\sum_{\pi\in \Auth} a_{\vec{y},\pi}$ and $\sum_{\pi\in \Auth} b_{\vec{w},\pi}$ are obtained by grouping
elements of the sums in Equations <ref> by $\Proj(\vec{y})$ and $\Proj(\vec{w})$, respectively.1337

But due to, because of200 Lemma <ref> we know that $\Proj$ preserves reversibility so the bound on the sum
$\sum_{\vec{w}\in \perm{\setInput_2}}b_{\vec{w}}= \sum_{\vec{w}\in \setInput_2}\sum_{\pi\in \Auth} b_{\vec{w},\pi}$ can be taken from Lemma <ref>,
$\sum_{\vec{w}\in \perm{\setInput_2}} b_{\vec{w}}\leq
\size{\Proj(\setInput_2)}\cdot \

Let $\setInput_1, \setInput_2$ be a partition of $\setInput$ into elements reversible and non-reversiblenonreversible1319 in $\perm{\setInput}$,
Suppose, $s_{max}\eqdef max(\setof{\size{\support{\vec{w}}}}{\vec{w}\in \setInput_2}).$
Let $\setSbar\subset \setD$ isbeNULL a set such that
$\support{\vec{v}}\subseteq \setSbar$$\vec{v}$ is supported by $\setSbar$1345 and

\begin{equation}
\size{\setSbar}=\size{\support{\vec{v}}} + \\
s_{max}\cdot \bigg(\size{\Proj(\setInput_2)}\cdot \
\setInput}}\bigg).
\end{equation}

Finally, let $\widetilde{\setInput_2} \subset \perm{\setInput_2}$ isbe1348 the set of all data vectors in
$\perm{\setInput}$$\perm{\setInput_2}$1348 that are supported by $\setSbar$.

Then $\vec{v}\in \sums{\N}{\perm{\setInput}}$ if,325 and only if,325

\[
\vec{v} =\sum_{\vec{y}\in \perm{\setInput_1}}  a_{\vec{y}} \vec{y} +\sum_{\vec{w}\in \widetilde{\setInput_2}} b_{\vec{w}} \vec{w} \text{ where } a_{\vec{y}}, b_{\vec{w}}\in \N.
\]

Note that the second sum is only over vectors supported by $\setSbar.$

Implication from right to left is trivial. Implication from left to right is thea1355 consequence of
Lemma <ref>.
$\vec{v} =\sum_{\vec{y}\in \perm{\setInput_1}}  a_{\vec{y}}' \vec{y} +\sum_{\vec{w}\in \perm{\setInput_2}} b_{\vec{w}}' \vec{w}.$

Let $\setShat$ be the union of supports of $\vec{w}\in \perm{\setInput_2}$ that appear with nonzero coefficients in the sum above.
Observe $\size{\setShat} +\size{\support{\vec{v}}}\leq \size{\setSbar}$ due to Lemma <ref> and the definition of $\size{\setSbar}$.
Let $\pi$ be a data permutation that
is the identity on $\support{\vec{v}}$ and injects $\setShat$ into $\setSbar$.
Then, $\vec{v}=\vec{v}\circ \pi^{-1}=\sum_{\vec{y}\in \perm{\setInput_1}}  a_{\vec{y}}' \vec{y}\circ\pi^{-1} +\sum_{\vec{w}\in \perm{\setInput_2}} b_{\vec{w}}'
\vec{w}\circ
\pi^{-1},$
as required (since $\vec{w}\circ
\pi^{-1}\in \widetilde{\setInput_2}$)1362.

Due toBecause of200 Theorem <ref>, in $\NETIME$ it is possible to construct an instance of the
$\Z$-solvability with data problem of exponential sizeexponential size instance of $\Z$-solvability with data problem1365, that has a solution
if,325 and only if,325
the original problem has a solution. Precisely, using the notation from Theorem <ref> we ask
$\vec{v}-\sum_{\vec{w}\in \setInput_2\circ \Pi} b_{\vec{w}} \vec{w} \in \sums{\Z}{\perm{\setInput_1}}$
we ask
$\vec{v}-\sum_{\vec{w}\in \widetilde{\setInput_2}} b_{\vec{w}} \vec{w} \in \sums{\Z}{\perm{\setInput_1}}$, where $\widetilde{\setInput_2}$
is defined in Theorem <ref>
1367. According to Theorem <ref>
it can be solved in $\ETIME.$ Thus Thus, 177the algorithm works in $\NETIME.$

The presented reduction works in the same way for a more general class of data vectors of the form $\ktuple{\setSizeK}{\setD}\xrightarrow{}
\ktuple{\dimension}{\Z}$.

§ CONCLUSIONS AND FUTURE WORK.

We have shown $\ETIME$ and $\PTIME$ upper complexity1372 bounds for the 1372$\N$- and $\Z$-solvability problems
over sets (unordered tuples) of data, respectively,
by (1) reducing the former problem to the latter one (with nondeterministic exponential blowup),
(2) reformulating the latter problem in terms of (weighted) hypergraphs,
and (3) solving the corresponding hypergraph problem by providing a local characterisation
testable in polynomial time.

The characterisation of $\Z$-solvability provided by Theorem <ref> identifies several simple to test properties that all together are equivalent to
$\Z$-solvability. Each of propertiesEach of the properties1378 is independent of others and may be used as a partial test for
non-reachabilitynonreachability107 in data nets.
It is not clear if in every industrial1380 application we should use all of

The proposed characterisation does not work for directed structures, as all weight$\weight{non}$ morphisms1381 of the following nontrivial graphsgraph1381 are $\vec{0}$.

[place/.style=circle,draw=!50,fill=!20,thick,inner sep=0pt,minimum size=4mm]
[place]      (A1)         $\da$;
[place]      (B1)       [left=of A1]  $\db$;
[->] (B1) [bend left] to node [above] $1$ (A1);
[->] (A1) [bend left]to node [below] $-1$ (B1) ;

Thus Thus, 177we should somehow refine the characterisation for data vectors going from ${\setSizeK}$-tuples to
$\dimension$-dimensional vectors of integer
numbersintegers1387, $\ktuple{\setSizeK}{\setD} \xrightarrow{} \ktuple{\dimension}{\Z}$.
For example, for directed graphs the condition
stated in Equation <ref> can be formulated as follows:
For every vertex $\da$ we define $\overrightarrow{\weight{da}}(\hypergraphH)=(out, in)$ where $out$ is the sum of all edges in $\hypergraphH$ outgoing fromleaving1389
and $in$ is the sum all
in $\hypergraphH$ incoming toentering1390 $\da$. Now, instead of

\begin{equation*}
{\weight{da}}(\hypergraphH) \in \sums \Z {\setof{{\weight{da'}}(\hypergraphH')}{\\ \hypergraphH' = ({\setVertices}', \mu')
\in
{\setInput}, \da' \in {\setVertices}'}}
\end{equation*}

we have

\begin{equation}
\label{eq:ass1_direc}
\overrightarrow{\weight{da}}(\hypergraphH) \in \sums \Z {\setof{\overrightarrow{\weight{da'}}(\hypergraphH')}{\\ \hypergraphH' = ({\setVertices}', \mu')
\in
{\setInput}, \da' \in {\setVertices}'}}
\end{equation}

This is still not sufficient due tobecause of200 the following example with all weights equal to1393 $\vec{0}$:

[place/.style=circle,draw=!50,fill=!20,thick,inner sep=0pt,minimum size=4mm]
[place]      (A)                       $\da$;
[place]      (B)       [below left=of A]  $\db$;
[place]      (C)      [below right=of A] $\dc$;
[->] (B) [bend left] to node [above] $-1$ (A);
[->] (A) [bend left]to node [above] $-1$ (C);
[->] (C) [bend left]to node [below] $-1$ (B);

[->] (A) to node [below] $1$ (B);
[->] (C)  to node [below] $1$ (A);
[->] (B)  to node [above] $1$ (C);

To deal with this example we need to define another invariant, namely for every pair of nodesverticesNULL its weight $\da,\db$ the
value of
$\weight{{da,db}}$1399 is a pair of numbers,numbers:1399
sum of edgestwo edges between vertices $\da$ and $\db$,1399 and the absolute value of their differencethe difference of the
weights of the two edges1399. Unfortunately, it is not clear how to generalise such invariants for hypergraphs.

Another approach to define weightsa definition of $\weight{non}$1401-1404 for directed hypergraphs is to linearly order vertices and add
only hyperedges that are oriented in the same way with
to the order. group edges depending on their orientation with respect to the order. Calculating $\weight{non}$ we add edges within the
groups.1401-1404 For example, if the order is $\db<\da<\dc$ then $\weight{da}$ of the triangle above is equal to $[-2,2]$.1401-1404
However, inIn1401-1404 this approach the weight depends on the orientation, which does not look as a desired solution.

Although we do not have the theorem which states that the $\Z$-solvability is equivalent to some
lifted version of local characterisation, the local characterizations may be useful.1406 Observe that1408 any of
described invariants  may be used as a partial test for the nonexistence of the solution. Indeed, they areis1408 homomorphisms from
data vectors in $\ktuple{\setSizeK}{\setD} \xrightarrow{} \ktuple{\dimension}{\Z}$ to $\ktuple{\dimension}{\Z} \cdot n$$\ktuple{\dimension\cdot
}$1409 for some $n\in \N$ depending on the
homomorphism (for example in case of the $(out, in)$ weight the value $n=2$). Thus Thus, 177we identified a family of
new heuristics that
can be used in the
analysis of data nets.

We also should mention that although in the proof of Theorem <ref> we use data vectors with the1413 image in $\ktuple{\dimension}{\Z}$ all proofs
workswork1414 for any Abelian groupgroups1414 in which
the system of equations <ref> has a unique solution. In the general case, it corresponds to the Abelian group in which
Lemma <ref> in Section <ref>1415 holds. ItLemma <ref>1415 speaks about maximality of the rank of some specific family of matrices.

We leave two interesting open problems.
First, concerning the complexity of the1417 $\N$-solvability, we leave the gapa gap1418 between
the $\NPTIME$ lower bound and our $\NETIME$ upper bound.
Currently, available methods seem not suitable for closing this gap.
Second, the line of research we establish in this paper calls for continuation, in particular for
investigation of the solvability problems over the ordered tuples of data.
Due toBecause of200 Remark <ref> we know that the problematic bit is a generalisation of the Theorem <ref>
In our opinion, the solution for this case should be possible by further development of
the techniquesbe within reach by further developing techniques1423 proposed in this paper.

§ ACKNOWLEDGMENT

Authors thank Prof. Sławomir Lasota as well as many anonymous conference reviewers for suggesting improvements.