0
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ 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 center 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." $\endgroup$
    – D.W.
    Commented Jun 5 at 20:27
  • $\begingroup$ @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?! $\endgroup$
    – C Marius
    Commented Jun 5 at 20:32
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Jun 5 at 20:36
  • $\begingroup$ @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 ... $\endgroup$
    – C Marius
    Commented Jun 5 at 20:38
  • $\begingroup$ Should I move the question to other StackExchange sites? ComputerScience Stack Exchange or ... ? $\endgroup$
    – C Marius
    Commented Jun 5 at 20:40

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – C Marius
    Commented Jun 13 at 9:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.