<p>The problem is that the sum <span class="math-container">$\sum x_i \alpha_{ij}$</span> is not in the set <span class="math-container">$\{0,1\}$</span> so that we don't get the linear system. But a nice try anyways.</p>

CC BY-SA 4.0
2024-06-13T09:13:16.767Z
it is in the set $\{0,1\}$ if we work in the $\mathbb{Z}_2$ ring. But that is trivial to solve after all, since it just means if the sum is even or odd.
C Marius
CC BY-SA 4.0
2024-06-10T09:20:13.270Z
2024-06-10T09:20:13.270Z
Mikko Pitkonen
<p>Consider a set of natural numbers <span class="math-container">$S \in \mathbb{N}^n$</span> for some <span class="math-container">$n \in \mathbb{N}$</span>. Assume that each number <span class="math-container">$s_i = S^T\cdot e_i$</span> meets <span class="math-container">$s_i \leq 2^m$</span> i.e. is written on at most <span class="math-container">$m$</span> number of digits, for some given <span class="math-container">$m \in \mathbb{N}$</span> and <span class="math-container">$e_i$</span> a column of the unit matrix. Let <span class="math-container">$T \in \mathbb{N}$</span> be a target. We ask if exists <span class="math-container">$x \in \{0,1\}^n$</span> with <span class="math-container">$x^T\cdot S = T$</span>. We propose the following approach. Assume
<span class="math-container">$$
s_i = \alpha_{i,0}\cdot 2^0 + \alpha_{i,1}\cdot 2^1 + ... + \alpha_{i,m-1}\cdot 2^{m-1}
$$</span> and
<span class="math-container">$$
T = \beta_{0}\cdot 2^0 + \beta_{1}\cdot 2^1 + ... + \beta_{m-1}\cdot 2^{m-1}
$$</span> We obtain the equation:
<span class="math-container">$$
\sum_{i=1}^n x_i \cdot \left( \alpha_{i,0}\cdot 2^0 + \alpha_{i,1}\cdot 2^1 + ... + \alpha_{i,m-1}\cdot 2^{m-1}\right) = \sum_{k=1}^m \beta_{k-1} \cdot 2^{k-1}
$$</span> or
<span class="math-container">$$
\sum_{i=1}^n x_i \cdot \sum_{k=1}^m \alpha_{i,k-1}\cdot 2^{k-1} = \sum_{k=1}^m 2^{k-1}\cdot \sum_{i=1}^n x_i \cdot \alpha_{i,k-1} = \sum_{k=1}^m \beta_{k-1}\cdot 2^{k-1}
$$</span> from where we get the equations:
<span class="math-container">\begin{align}
\begin{cases}
\alpha_{1,0} \cdot x_1 + ... + \alpha_{n,0}\cdot x_n = \beta_0\\
... \\
\alpha_{1,m-1} \cdot x_1 + ... + \alpha_{n,m-1}\cdot x_n = \beta_{m-1}
\end{cases} \iff \begin{bmatrix} \alpha_{1,0} &amp;... &amp;\alpha_{n,0}\\ \vdots &amp;\ddots &amp;\vdots\\ \alpha_{1,m-1} &amp;... &amp;\alpha_{n,m-1}\end{bmatrix} \cdot \begin{bmatrix} x_1\\ \vdots \\ x_n\end{bmatrix} = \begin{bmatrix} \beta_{1}\\ \vdots \\ \beta_{m-1}\end{bmatrix}
\end{align}</span> This is a binary linear system. It can be also written as:</p>
<p><span class="math-container">\begin{align}
\begin{cases}
\alpha_{1,0} \cdot x_1 + ... + \alpha_{n,0}\cdot x_n = \beta_0\\
... \\
\alpha_{1,m-1} \cdot x_1 + ... + \alpha_{n,m-1}\cdot x_n = \beta_{m-1}
\end{cases} \iff \begin{cases} \alpha_{1,0} \wedge x_1 \otimes ... \otimes \alpha_{n,0}\wedge x_n = \beta_0\\
... \\
\alpha_{1,m-1} \wedge x_1 \otimes ... \otimes \alpha_{n,m-1}\wedge x_n = \beta_{m-1}
\end{cases}
\end{align}</span>  where <span class="math-container">$\wedge$</span> is the logical &quot;AND&quot; and <span class="math-container">$\otimes$</span> is the logical &quot;XOR&quot;.</p>
<h2>Question</h2>
<p>Can this linear system modulo 2 be solved in polynomial time using Gaussian elimination modulo 2? If so, then I think <span class="math-container">$x$</span> is a solution to Subset Sum in some sense. But I do not understand what it means ...</p>

CC BY-SA 4.0
2024-06-05T20:27:05.550Z
That's a lot to read.  Isn't the answer obviously yes, any linear system of equations mod 2 can be solved with Gaussian elimination?  How is this a research-level question?  Our [help/on-topic] requires you to show your progress and provide context, e.g., "You should only post questions you're actually seriously thinking about. Users are expected to do their part and try to answer their question by themselves before posting them on cstheory and asking for help from others. [..] Try to make your question interesting for others by providing some background knowledge."
D.W.
CC BY-SA 4.0
2024-06-05T20:32:49.270Z
@D.W Thank you for your attention sir! Well, in this case, it means the Subset Sum can be solved in polynomial time isn't it? The "long derivation" shows that the solution the the linear system modulo 2 is actually the solution to the Subset Sum. Do I get this right?!
C Marius
CC BY-SA 4.0
2024-06-05T20:36:17.270Z
Sorry.  That's not what this site is for.  This site is intended to build an archive of knowledge that will be useful for others, in the form of high-quality questions and answers; and our scope is theoretical CS, which means research-level questions that, e.g., a grad student in theoretical CS might encounter.  We're not here to check the correctness of your proposed proof that P=NP, or to spot undergraduate-level errors in understanding.  Please read our help center to learn more about this site's scope.
D.W.
CC BY-SA 4.0
2024-06-05T20:38:52.233Z
@D.W I do apologize! I came up with this simple approach to this problem following a discussion with a colleague regarding p-adic numbers ...
C Marius
CC BY-SA 4.0
2024-06-05T20:40:40.357Z
Should I move the question to other StackExchange sites? ComputerScience Stack Exchange or ... ?
C Marius
CC BY-SA 4.0
2024-06-05T21:02:31.110Z
I guess equality modulo 2 is trivial as it just implies to find a subset whose sum is even or  odd respectively depending on the parity of $T$.
C Marius
<linear-algebra><subset-sum>
Solution to Subset Sum Problem (in some sense) using Gaussian elimination modulo 2
C Marius
# Solution to Subset Sum Problem (in some sense) using Gaussian elimination modulo 2

(Asked by: username_0 on 2024-06-05)

Consider a set of natural numbers $S \in \mathbb{N}^n$ for some $n \in \mathbb{N}$. Assume that each number $s\_i = S^T\cdot e\_i$ meets $s\_i \leq 2^m$ i.e. is written on at most $m$ number of digits, for some given $m \in \mathbb{N}$ and $e\_i$ a column of the unit matrix. Let $T \in \mathbb{N}$ be a target. We ask if exists $x \in \{0,1\}^n$ with $x^T\cdot S = T$. We propose the following approach. Assume
$$
s\_i = \alpha\_{i,0}\cdot 2^0 + \alpha\_{i,1}\cdot 2^1 + ... + \alpha\_{i,m-1}\cdot 2^{m-1}
$$ and
$$
T = \beta\_{0}\cdot 2^0 + \beta\_{1}\cdot 2^1 + ... + \beta\_{m-1}\cdot 2^{m-1}
$$ We obtain the equation:
$$
\sum\_{i=1}^n x\_i \cdot \left( \alpha\_{i,0}\cdot 2^0 + \alpha\_{i,1}\cdot 2^1 + ... + \alpha\_{i,m-1}\cdot 2^{m-1}\right) = \sum\_{k=1}^m \beta\_{k-1} \cdot 2^{k-1}
$$ or
$$
\sum\_{i=1}^n x\_i \cdot \sum\_{k=1}^m \alpha\_{i,k-1}\cdot 2^{k-1} = \sum\_{k=1}^m 2^{k-1}\cdot \sum\_{i=1}^n x\_i \cdot \alpha\_{i,k-1} = \sum\_{k=1}^m \beta\_{k-1}\cdot 2^{k-1}
$$ from where we get the equations:
\begin{align}
\begin{cases}
\alpha\_{1,0} \cdot x\_1 + ... + \alpha\_{n,0}\cdot x\_n = \beta\_0\\
... \\
\alpha\_{1,m-1} \cdot x\_1 + ... + \alpha\_{n,m-1}\cdot x\_n = \beta\_{m-1}
\end{cases} \iff \begin{bmatrix} \alpha\_{1,0} &... &\alpha\_{n,0}\\ \vdots &\ddots &\vdots\\ \alpha\_{1,m-1} &... &\alpha\_{n,m-1}\end{bmatrix} \cdot \begin{bmatrix} x\_1\\ \vdots \\ x\_n\end{bmatrix} = \begin{bmatrix} \beta\_{1}\\ \vdots \\ \beta\_{m-1}\end{bmatrix}
\end{align} This is a binary linear system. It can be also written as:

\begin{align}
\begin{cases}
\alpha\_{1,0} \cdot x\_1 + ... + \alpha\_{n,0}\cdot x\_n = \beta\_0\\
... \\
\alpha\_{1,m-1} \cdot x\_1 + ... + \alpha\_{n,m-1}\cdot x\_n = \beta\_{m-1}
\end{cases} \iff \begin{cases} \alpha\_{1,0} \wedge x\_1 \otimes ... \otimes \alpha\_{n,0}\wedge x\_n = \beta\_0\\
... \\
\alpha\_{1,m-1} \wedge x\_1 \otimes ... \otimes \alpha\_{n,m-1}\wedge x\_n = \beta\_{m-1}
\end{cases}
\end{align} where $\wedge$ is the logical "AND" and $\otimes$ is the logical "XOR".

## Question

Can this linear system modulo 2 be solved in polynomial time using Gaussian elimination modulo 2? If so, then I think $x$ is a solution to Subset Sum in some sense. But I do not understand what it means ...

**Tags:** linear-algebra, subset-sum
> **Comments:**
> **username_1**: That's a lot to read.  Isn't the answer obviously yes, any linear system of equations mod 2 can be solved with Gaussian elimination?  How is this a research-level question?  Our [help/on-topic] requires you to show your progress and provide context, e.g., "You should only post questions you're actually seriously thinking about. Users are expected to do their part and try to answer their question by themselves before posting them on cstheory and asking for help from others. [..] Try to make your question interesting for others by providing some background knowledge."  
> **username_0**: @D.W Thank you for your attention sir! Well, in this case, it means the Subset Sum can be solved in polynomial time isn't it? The "long derivation" shows that the solution the the linear system modulo 2 is actually the solution to the Subset Sum. Do I get this right?!  
> **username_1**: Sorry.  That's not what this site is for.  This site is intended to build an archive of knowledge that will be useful for others, in the form of high-quality questions and answers; and our scope is theoretical CS, which means research-level questions that, e.g., a grad student in theoretical CS might encounter.  We're not here to check the correctness of your proposed proof that P=NP, or to spot undergraduate-level errors in understanding.  Please read our help center to learn more about this site's scope.  
> **username_0**: @D.W I do apologize! I came up with this simple approach to this problem following a discussion with a colleague regarding p-adic numbers ...  
> **username_0**: Should I move the question to other StackExchange sites? ComputerScience Stack Exchange or ... ?  
> **username_0**: I guess equality modulo 2 is trivial as it just implies to find a subset whose sum is even or  odd respectively depending on the parity of $T$.  

---

## 1 answers

### Answer by username_2 on 2024-06-10. Score: 1

The problem is that the sum $\sum x\_i \alpha\_{ij}$ is not in the set $\{0,1\}$ so that we don't get the linear system. But a nice try anyways.

> **Comments:**
> **username_0**: it is in the set $\{0,1\}$ if we work in the $\mathbb{Z}_2$ ring. But that is trivial to solve after all, since it just means if the sum is even or odd.  

---

