1

Let matrix $M \in \{0,1\}^{r \times (c+1)r}$ for some $c \in \Bbb Z_{+}$ be given.

Is it NP-complete to decide if $\exists u \in \{0,1\}^{1 \times r}$ $:$$\prod_i v_i \in 2\Bbb Z+1$ where $v=uM$?

Turbo
  • 6,221
  • Let me rephrase this problem: "You are given a circuit of depth 2; the last gate is an and gate. Feeding into it is a number of parity gates; feeding into each of these is a bunch of variables (possibly none of them), distinct and not negated. Is the circuit satisfiable?" (Note that I am ignoring the restriction that the number of parity gates be a multiple of the number of variables, because it seems irrelevant -- one can always add more parity gates with nothing feeding in.) – Harry Altman Aug 20 '13 at 20:48
  • You mean depth $3$- in the form of $\prod\sum\prod$ where the left $\prod$ is $\prod_i v_i$? Is this NP-Complete? – Turbo Aug 20 '13 at 21:17
  • No, depth 2. There is no rightmost product; a 0 simply means the variable is not included, a 1 means it is. – Harry Altman Aug 21 '13 at 00:45

1 Answers1

1

The problem is in $P$, and hence not $NP$-complete unless $P=NP$.

Because we are only concerned with parity, we can treat the matrices and vectors as having entries lying in $\mathbb{F}_2$. Then the condition just becomes $uM=j$, where $j$ is the all-ones row vector. This can be solved with Gaussian elimination.

Harry Altman
  • 4,652
  • So is this problem in P as well? Let matrix $M \in {0,1}^{r \times (c+1)r}$ ($c>0$), let function $f:\Bbb Z^{} \rightarrow \pm1$ be isomorphic to $\bmod2$ and let $\alpha \in \Bbb Z \cap (0,s)$ be given.

    Problem A:Decide if $\exists u \in {0,1}^{1 \times r}$ with $v=uM$: ${\sum_{i=1}^{(c+1)r}f(v_{i})^{}} \geq \alpha$?

    For $\underline{worst case}$ of $\alpha = (c+1)r$, the problem I put up and this are same. So is Problem A in P too?

     – Turbo Aug 21 '13 at 17:26
  • Or may be on easier cases the problem is hard? If so, is there a proof for this problem t be NP-complete? – Turbo Aug 21 '13 at 17:33
  • I'm having trouble understanding what you mean when you talk about $f$. – Harry Altman Aug 21 '13 at 18:02
  • f is just a function. say if n mod 2 is 1 then pick f(n)=-1 else pick f(n)=1. The other choice of f(odd)=1 and f(even)=-1 is equally valid. This is what I mean by f is isomorphic to mod 2. – Turbo Aug 21 '13 at 18:03
  • So, in other words, either $f(n)=(-1)^n$, or $f(n)=-(-1)^n$? Yes I don't think that is standard usage of "isomorphic". – Harry Altman Aug 21 '13 at 18:35
  • That is a succinct way. So is Problem A in P too since for worst case $\alpha=(c+1)r$ it is in P? – Turbo Aug 21 '13 at 18:37
  • No, that doesn't follow. Suppose for instance $\alpha=s/2$; solving $\alpha=s$ won't help you very much here, since there could be many that satisfy the looser constraint, but none that satisfy the tighter constraint. (Also, why do you keep insisting that the number of columns is a multiple of the number of rows? That seems irrelevant.) – Harry Altman Aug 21 '13 at 19:05
  • It is irrelevant. Just for my convenience I added. You can just use any s > r. Regarding the problem itself - so you think this problem is harder and is NP-Complete? Is there a proof you could provide? – Turbo Aug 21 '13 at 19:10
  • 1
    I have no idea. I haven't really thought about it. By the way, $f$ isn't really doing any work -- this is essentially about counting ones (or odd numbers if you don't reduce mod 2 for some reason). If $f(n)=(-1)^n$, you want the number of 1s above some threshold. If $f(n)=-(-1)^n$, you want it below some threshold. (In the latter case, this can always be achieved by u=0.) – Harry Altman Aug 21 '13 at 21:14
  • I want it above some threshold for both cases. If you happen to solve the problem, please drop a line and I would appreciate the effort. – Turbo Aug 21 '13 at 21:36
  • 1
    The sum of $f$ would be above some threshold; the number of ones would be below some threshold. – Harry Altman Aug 21 '13 at 22:00
  • @Altman If you found a proof please let me know. I am stuck on a research problem here. – Turbo Aug 22 '13 at 20:01