<p>Let $G_{ij} \in \{0,1\}$ for $i$ from $1$ to $r$ and $j$ from $1$ to $s&gt;r$ be fixed.</p>

<p>Is deciding $\exists u_1,u_2,\dots,u_r$ that satisfies the following formula <strong>NP-Complete</strong>? $$\otimes_{j=1}^{s}\oplus_{i=1}^{r}u_i \otimes G_{ij} = 1$$</p>

<p>($a\oplus b=0 \iff a=b$ and $a \otimes b = 1 \iff a=b=1$)</p>

<p>What if it is given the set of $G_{ij} = 1$ for each $j$ has cardinality that satisfies one of the two cases:</p>

<p>$(1)$ Cardinality atmost $d$ for some constant $d &gt; 0$? </p>

<p>$(2)$ Cardinality atmost $dr^{\epsilon}$ for some constant $d &gt; 0$ and some $\epsilon \in (0,1)$? </p>

CC BY-SA 3.0
2013-08-20T22:39:49.003Z
What if you take $u_i=1$ for all $i$ ?
Xavier Labouze
CC BY-SA 3.0
2013-08-20T22:41:53.720Z
Doubt it will work for all instances of $Gij$! The formula depends on $Gij$ as well. Try $s=3$,$r=2$ and all $Gij=1$. You will get $0$.
Turbo
CC BY-SA 3.0
2013-08-20T22:43:51.540Z
hold on I made a mistake.
Turbo
CC BY-SA 3.0
2013-08-20T22:45:50.020Z
Thankyou. I meant $1+1=0$ and $1+1+1=1$. I understand the folly that $1\vee 1=1$. Corrected now.
Turbo
CC BY-SA 3.0
2013-08-20T22:55:09.923Z
You mean $a \otimes b = 1 \iff a=b$ (and not $a=b=1$) ?
Xavier Labouze
CC BY-SA 3.0
2013-08-20T22:55:55.890Z
no I want $0 \otimes 0 = 0$ and hence the relation.
Turbo
CC BY-SA 3.0
2013-08-20T22:57:57.453Z
So it is the same as an AND and my first comment remains...
Xavier Labouze
CC BY-SA 3.0
2013-08-20T23:04:27.443Z
Let $Gij=1$ for $i=1,2$ and $j=1,2,3$. For each $j$, then $u1\otimes G1j = 1$ and $u1\otimes G1j \oplus u2\otimes G2j = 1 \oplus 1 =0$. So $\otimes_{j=1}^{3}0=0$. We do not have valuation to $1$.
Turbo
CC BY-SA 3.0
2013-08-20T23:18:32.723Z
Your first comment came from my 'XOR' being wrong.
Turbo
CC BY-SA 3.0
2013-08-21T05:08:20.223Z
I may be wrong, but isn't this just solving the linear equation $\mathbf{uG}=\mathbf{1}$ over the finite field $\mathbb{Z}_2$? If so, you could just use Gaussian elimination.
Shitikanth
CC BY-SA 3.0
2013-08-21T10:06:06.280Z
Take $r$ is even and/or $s>r$.
Turbo
<np-complete>
Complexity of a particular problem
Turbo
# Complexity of a particular problem

(Asked by: username_0 on 2013-08-20)

Let $G\_{ij} \in \{0,1\}$ for $i$ from $1$ to $r$ and $j$ from $1$ to $s>r$ be fixed.

Is deciding $\exists u\_1,u\_2,\dots,u\_r$ that satisfies the following formula **NP-Complete**? $$\otimes\_{j=1}^{s}\oplus\_{i=1}^{r}u\_i \otimes G\_{ij} = 1$$

($a\oplus b=0 \iff a=b$ and $a \otimes b = 1 \iff a=b=1$)

What if it is given the set of $G\_{ij} = 1$ for each $j$ has cardinality that satisfies one of the two cases:

$(1)$ Cardinality atmost $d$ for some constant $d > 0$?

$(2)$ Cardinality atmost $dr^{\epsilon}$ for some constant $d > 0$ and some $\epsilon \in (0,1)$?

**Tags:** np-complete

> **Comments:**
> **username_1**: What if you take $u_i=1$ for all $i$ ?  
> **username_0**: Doubt it will work for all instances of $Gij$! The formula depends on $Gij$ as well. Try $s=3$,$r=2$ and all $Gij=1$. You will get $0$.  
> **username_0**: hold on I made a mistake.  
> **username_0**: Thankyou. I meant $1+1=0$ and $1+1+1=1$. I understand the folly that $1\vee 1=1$. Corrected now.  
> **username_1**: You mean $a \otimes b = 1 \iff a=b$ (and not $a=b=1$) ?  
> **username_0**: no I want $0 \otimes 0 = 0$ and hence the relation.  
> **username_1**: So it is the same as an AND and my first comment remains...  
> **username_0**: Let $Gij=1$ for $i=1,2$ and $j=1,2,3$. For each $j$, then $u1\otimes G1j = 1$ and $u1\otimes G1j \oplus u2\otimes G2j = 1 \oplus 1 =0$. So $\otimes_{j=1}^{3}0=0$. We do not have valuation to $1$.  
> **username_0**: Your first comment came from my 'XOR' being wrong.  
> **username_2**: I may be wrong, but isn't this just solving the linear equation $\mathbf{uG}=\mathbf{1}$ over the finite field $\mathbb{Z}_2$? If so, you could just use Gaussian elimination.  
> **username_0**: Take $r$ is even and/or $s>r$.  

---

## 0 answers

