<p>Yes, it is NP-complete, by reduction from 3SAT.  In particular, we will go through an intermediate problem, which I will define as follows:</p>

<p><strong>Definition.</strong>  The <em>1-to-3 of $k$ problem</em> is as follows: given $n$ sets $S_1,\dots,S_n$, decide whether there exists $y_1,\dots,y_m \in \{0,1\}$ such that $1 \le \sum_{j\in S_i} y_j \le 3$ holds for all $i$.</p>

<p><strong>Theorem 1.</strong> The 1-to-3 of $k$ problem is at least as hard as 3SAT.</p>

<p><em>Proof:</em> Suppose we have a formula $\varphi$ with $n$ clauses over $m$ variables, $x_1,\dots,x_m$.  Introduce $m'=2m$ variables, $y_1,\dots,y_m$.  The intent is that these will correspond to the $2m$ literals $x_1,\dots,x_m,\neg x_1,\dots,\neg x_m$ (e.g., $y_i=1$ if and only if $x_i=\text{True}$; $y_{m+i}=1$ if and only if $x_i=\text{False}$); we will introduce a few sets to enforce this intent.  There are $n'=n+m+\lceil m/3\rceil$ sets, as follows:</p>

<ul>
<li><p>First, there are $n$ sets, one for each clause of $\varphi$.  If $\varphi$ has the clause $(y_a\lor y_b\lor y_c)$ (where $y_a,y_b,y_c$ are three literals), then we'll add a set $S=\{a,b,c\}$ to enforce that at least one of $y_a,y_b,y_c$ must be true.</p></li>
<li><p>The next $m$ sets enforce that $x_i \lor \neg x_i$ is true for all $i$.  In particular, for each $i$, we add a set to enforce that at least one of $x_i, \neg x_i$ must be true, e.g., the set $S=\{i,i+m\}$ (if $y_i$ corresponds to $x_i$ and $y_{i+m}$ corresponds to $\neg x_i$).</p></li>
<li><p>Finally, the last $\lceil m/3 \rceil$ sets enforce that $x_i$ and $\neg x_i$ are not allowed to both be true.  We'll do this by enforcing that one, two, or three of $x_1,\neg x_1,x_2,\neg x_2,x_3,\neg x_3$ are true (e.g., the set $S=\{1,2,3,m+1,m+2,m+3\}$), and that at least one, two, or three of $x_4,\neg x_4,x_5,\neg x_5,x_6,\neg x_6$ are true (e.g., the set $S=\{4,5,6,m+4,m+5,m+6\})$, and so on.   Notice that, thanks to the previous category of sets, surely at least three of these 6 literals will be true, so asking that "one, two, or three should be true" amounts to asking that exactly three of them must be true -- which has the desired effect.</p></li>
</ul>

<p>Finally, it is easy to see that this 1-to-3 of $k$ problem has a solution if and only if $\varphi$ has a satisfying assignment.  That completes the proof.</p>

<p><strong>Theorem 2.</strong> Your problem is at least as hard as the 1-to-3 of $k$ problem.</p>

<p><em>Proof.</em> Suppose we have a 1-to-3 of $k$ problem with $s$ sets over variables $y_1,\dots,y_r$.    Define $f(0)=0$, $f(1)=1$, $f(2)=1$, $f(3)=1$, and $f(k)=0$ for all $k&gt;3$.  Define the matrix $M$ based upon the sets $S_1,\dots,S_s$.  In particular, if $S_i=\{a,b,c,\dots\}$, the $i$th column of $M$ has a 1 in the $a$th, $b$th, $c$th, $\ldots$ rows and is zero elsewhere ($M_{j,i}=1$ if and only if $j \in S_i$).  Finally, set $\alpha=s$.</p>

<p>Now $|f(v)|\ge \alpha$ holds if and only if $f(v_1)=f(v_2)=\dots=f(v_s)=1$.  Thus, this choice of $f$ and setting of $\alpha$ ensures that the only way to satisfy the equation $|f(v)|\ge \alpha$ is if each $v_i$ is 1, 2, or 3.  If we focus on $v_i$, corresponding to the set $S_i=\{a,b,c,\dots\}$, then $f(v_i)=1$ if and only if $1 \le y_a+y_b+y_c+\dots \le 3$.  Therefore, this instance of your problem has a solution if and only if the original 1-to-3 of $k$ instance does.</p>

CC BY-SA 3.0
2013-08-14T03:48:00.960Z
You can simplify the construction if you start from NAE-3SAT restricted to instances where all literals are unnegated. Then the construction in your first paragraph works, just set $f(i) = 1$ if and only if $i \in \{1, 2\}$. The unnegated NAE-3SAT problem (sometimes called E3-Set-Splitting) is known to be NP-hard and also hard to approximate to within a fixed constant factor, see  this paper by Guruswami: http://www.cs.cmu.edu/~venkatg/pubs/papers/ss-jl.ps.
Sasho Nikolov
CC BY-SA 3.0
2013-08-14T03:56:44.487Z
Nice!  That's a cleaner reduction.  Thank you, @SashoNikolov.  Do you want to post it separately as a separate answer, in case the original poster wants to mark it as the accepted answer?
D.W.
CC BY-SA 3.0
2013-08-14T10:21:34.000Z
Trying to grasp here. You seem to be proving deciding there exists $u:|f(v)| = |f(uM)| = s$ is NP-complete for a particular function. Since $s$ upper bounds any other selection of $\alpha \leq s$, the technique proves NP-complete for any $|f(v)| \geq \alpha$ for this $f$ (since NP-complete for max possible $s$). Is the interpretation correct? Secondly, since the technique shows NP-completeness for this selection of function $f$, it is NP-complete for any other non-trivial function (Eg: legendre symbol, modulo primes operations, random fixed assignment etc)? Is this interpretation correct too?
Turbo
CC BY-SA 3.0
2013-08-14T10:22:58.193Z
Can I enlarge the set $\pm1$ to $−s_1,s_1+1,⋯−1,0,1,…,s_2−1,s_2$ with $s_1 \neq s_2$ and still preserve NP-completeness?
Turbo
CC BY-SA 3.0
2013-08-14T11:53:52.177Z
@Arul, the answer to your questions are: Yes (NP-completeness is about worst-case hardness, so it suffices to show that at least some instances of the problem are hard), No (not necessarily; it depends whether the reduction can be performed), Yes (you can easily adjust the reduction: simply set $f(1)=f(2)=f(3)=s_2$, $f(x)=0$ for all other $x$, and $\alpha=s\times s_2$).
D.W.
CC BY-SA 3.0
2013-08-14T18:41:56.527Z
@Arul, this is not a forum: if you have a different question, you should probably post a separate question with the correct set of requirements.  But before you do that, make sure you take note that this site is for research-level questions in theoretical computer science.  Make sure you have a solid understanding of NP-completeness and reductions.  Your follow-up questions make me think you might be better served by first brushing up on your knowledge in this area, or by asking some more basic questions on CS.StackExchange, rather than here which is for research-level questions.
D.W.
CC BY-SA 3.0
2013-08-14T19:07:55.037Z
well I am not from tcs... sorry to make this post here. was facing a problem which reduced to this in my field
Turbo
CC BY-SA 3.0
2013-08-14T03:29:10.847Z
2013-08-14T03:59:01.170Z
2013-08-14T03:59:01.170Z
D.W.
<p>Let matrix $M \in \{0,1\}^{r \times s}$ ($s&gt;r$), let function $f:\Bbb Z^{} \rightarrow \pm1$ and let $\alpha \in \Bbb Z \cap (0,s)$ be given. </p>

<p>Is it NP-complete to decide if $\exists u \in \{0,1\}^{1 \times r}$ with $v=uM$: $|f(v)| = {\sum_{i=1}^{s}f(v_{i})^{}} \geq \alpha$?</p>

CC BY-SA 3.0
2013-08-13T16:30:36.950Z
$\|f(v)\|_2^2 = s$ for all $v$, since $f(v) \in \{\pm 1\}^s$. also what does the probability mean? is $f$ a random variable? how is it specified in the computational problem?
Sasho Nikolov
CC BY-SA 3.0
2013-08-13T16:45:42.563Z
Sorry had something else in mind.
Turbo
CC BY-SA 3.0
2013-08-13T17:04:50.123Z
$f(⋅)$ is a function picked randomly from all functions from $\Bbb Z → \pm1$.
Turbo
CC BY-SA 3.0
2013-08-13T17:26:47.287Z
But $f$ needs to be specified to an algorithm if you are going to talk about complexity classes. I am guessing you specify $f(1), \ldots, f(r)$ since these are the only relevant values. Then how does $f$ being random come into the problem? You still want to find $u$ for the specific $f$ given to the algorithm. Is it that you are ok if an algorithm fails with small probability, where the probability is over the choice of $f$? In that case NP-hardness is not the right notion, you have an average case complexity problem.
Sasho Nikolov
CC BY-SA 3.0
2013-08-13T17:53:26.143Z
Ok. Let me modify to the basic case I need. And then I can look into details myself. Thankyou for the comments.
Turbo
CC BY-SA 3.0
2013-08-13T21:40:37.257Z
There is no uniform distribution on all functions from $\mathbb{Z} \to \pm 1$.
Mahdi Cheraghchi
CC BY-SA 3.0
2013-08-15T16:01:00.333Z
@JAS while I agree that a question should not be a moving target, I like the question where $f$ is the Möbius function (you did mention that in a comment, didn't you?) and (in view of Sarnak's conjecture and the intuition that the Möbius function is pseudorandom) it might be a good way to instantiate a "derandomized" version of your original question where $f$ was random. I would encourage you to ask that question separately (it's definitely research level), with some motivation about why you care about it (for example how it comes up in your research).
Sasho Nikolov
CC BY-SA 3.0
2013-08-15T17:49:50.460Z
@SashoNikolov I think even with $f$ being $mod$ $2$ operation with $0$ mapped to $1$ and $1$ to $-1$ is still a hard problem. If I can get an answer for that it will be great.
Turbo
CC BY-SA 3.0
2013-08-15T20:34:42.817Z
I think you should ask both versions with some motivation as a new question.
Sasho Nikolov
<np-complete>
Complexity of a linear algebra problem
Turbo
# Complexity of a linear algebra problem

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

Let matrix $M \in \{0,1\}^{r \times s}$ ($s>r$), let function $f:\Bbb Z^{} \rightarrow \pm1$ and let $\alpha \in \Bbb Z \cap (0,s)$ be given.

Is it NP-complete to decide if $\exists u \in \{0,1\}^{1 \times r}$ with $v=uM$: $|f(v)| = {\sum\_{i=1}^{s}f(v\_{i})^{}} \geq \alpha$?

**Tags:** np-complete

> **Comments:**
> **username_1**: $\|f(v)\|_2^2 = s$ for all $v$, since $f(v) \in \{\pm 1\}^s$. also what does the probability mean? is $f$ a random variable? how is it specified in the computational problem?  
> **username_0**: Sorry had something else in mind.  
> **username_0**: $f(⋅)$ is a function picked randomly from all functions from $\Bbb Z → \pm1$.  
> **username_1**: But $f$ needs to be specified to an algorithm if you are going to talk about complexity classes. I am guessing you specify $f(1), \ldots, f(r)$ since these are the only relevant values. Then how does $f$ being random come into the problem? You still want to find $u$ for the specific $f$ given to the algorithm. Is it that you are ok if an algorithm fails with small probability, where the probability is over the choice of $f$? In that case NP-hardness is not the right notion, you have an average case complexity problem.  
> **username_0**: Ok. Let me modify to the basic case I need. And then I can look into details myself. Thankyou for the comments.  
> **username_2**: There is no uniform distribution on all functions from $\mathbb{Z} \to \pm 1$.  
> **username_1**: @JAS while I agree that a question should not be a moving target, I like the question where $f$ is the Möbius function (you did mention that in a comment, didn't you?) and (in view of Sarnak's conjecture and the intuition that the Möbius function is pseudorandom) it might be a good way to instantiate a "derandomized" version of your original question where $f$ was random. I would encourage you to ask that question separately (it's definitely research level), with some motivation about why you care about it (for example how it comes up in your research).  
> **username_0**: @SashoNikolov I think even with $f$ being $mod$ $2$ operation with $0$ mapped to $1$ and $1$ to $-1$ is still a hard problem. If I can get an answer for that it will be great.  
> **username_1**: I think you should ask both versions with some motivation as a new question.  

---

## 1 answers

### Answer by username_3 on 2013-08-14. Score: 2 | Accepted answer

Yes, it is NP-complete, by reduction from 3SAT. In particular, we will go through an intermediate problem, which I will define as follows:

**Definition.** The *1-to-3 of $k$ problem* is as follows: given $n$ sets $S\_1,\dots,S\_n$, decide whether there exists $y\_1,\dots,y\_m \in \{0,1\}$ such that $1 \le \sum\_{j\in S\_i} y\_j \le 3$ holds for all $i$.

**Theorem 1.** The 1-to-3 of $k$ problem is at least as hard as 3SAT.

*Proof:* Suppose we have a formula $\varphi$ with $n$ clauses over $m$ variables, $x\_1,\dots,x\_m$. Introduce $m'=2m$ variables, $y\_1,\dots,y\_m$. The intent is that these will correspond to the $2m$ literals $x\_1,\dots,x\_m,\neg x\_1,\dots,\neg x\_m$ (e.g., $y\_i=1$ if and only if $x\_i=\text{True}$; $y\_{m+i}=1$ if and only if $x\_i=\text{False}$); we will introduce a few sets to enforce this intent. There are $n'=n+m+\lceil m/3\rceil$ sets, as follows:

* First, there are $n$ sets, one for each clause of $\varphi$. If $\varphi$ has the clause $(y\_a\lor y\_b\lor y\_c)$ (where $y\_a,y\_b,y\_c$ are three literals), then we'll add a set $S=\{a,b,c\}$ to enforce that at least one of $y\_a,y\_b,y\_c$ must be true.
* The next $m$ sets enforce that $x\_i \lor \neg x\_i$ is true for all $i$. In particular, for each $i$, we add a set to enforce that at least one of $x\_i, \neg x\_i$ must be true, e.g., the set $S=\{i,i+m\}$ (if $y\_i$ corresponds to $x\_i$ and $y\_{i+m}$ corresponds to $\neg x\_i$).
* Finally, the last $\lceil m/3 \rceil$ sets enforce that $x\_i$ and $\neg x\_i$ are not allowed to both be true. We'll do this by enforcing that one, two, or three of $x\_1,\neg x\_1,x\_2,\neg x\_2,x\_3,\neg x\_3$ are true (e.g., the set $S=\{1,2,3,m+1,m+2,m+3\}$), and that at least one, two, or three of $x\_4,\neg x\_4,x\_5,\neg x\_5,x\_6,\neg x\_6$ are true (e.g., the set $S=\{4,5,6,m+4,m+5,m+6\})$, and so on. Notice that, thanks to the previous category of sets, surely at least three of these 6 literals will be true, so asking that "one, two, or three should be true" amounts to asking that exactly three of them must be true -- which has the desired effect.

Finally, it is easy to see that this 1-to-3 of $k$ problem has a solution if and only if $\varphi$ has a satisfying assignment. That completes the proof.

**Theorem 2.** Your problem is at least as hard as the 1-to-3 of $k$ problem.

*Proof.* Suppose we have a 1-to-3 of $k$ problem with $s$ sets over variables $y\_1,\dots,y\_r$. Define $f(0)=0$, $f(1)=1$, $f(2)=1$, $f(3)=1$, and $f(k)=0$ for all $k>3$. Define the matrix $M$ based upon the sets $S\_1,\dots,S\_s$. In particular, if $S\_i=\{a,b,c,\dots\}$, the $i$th column of $M$ has a 1 in the $a$th, $b$th, $c$th, $\ldots$ rows and is zero elsewhere ($M\_{j,i}=1$ if and only if $j \in S\_i$). Finally, set $\alpha=s$.

Now $|f(v)|\ge \alpha$ holds if and only if $f(v\_1)=f(v\_2)=\dots=f(v\_s)=1$. Thus, this choice of $f$ and setting of $\alpha$ ensures that the only way to satisfy the equation $|f(v)|\ge \alpha$ is if each $v\_i$ is 1, 2, or 3. If we focus on $v\_i$, corresponding to the set $S\_i=\{a,b,c,\dots\}$, then $f(v\_i)=1$ if and only if $1 \le y\_a+y\_b+y\_c+\dots \le 3$. Therefore, this instance of your problem has a solution if and only if the original 1-to-3 of $k$ instance does.

> **Comments:**
> **username_1**: You can simplify the construction if you start from NAE-3SAT restricted to instances where all literals are unnegated. Then the construction in your first paragraph works, just set $f(i) = 1$ if and only if $i \in \{1, 2\}$. The unnegated NAE-3SAT problem (sometimes called E3-Set-Splitting) is known to be NP-hard and also hard to approximate to within a fixed constant factor, see  this paper by Guruswami: http://www.cs.cmu.edu/~venkatg/pubs/papers/ss-jl.ps.  
> **username_3**: Nice!  That's a cleaner reduction.  Thank you, @SashoNikolov.  Do you want to post it separately as a separate answer, in case the original poster wants to mark it as the accepted answer?  
> **username_0**: Trying to grasp here. You seem to be proving deciding there exists $u:|f(v)| = |f(uM)| = s$ is NP-complete for a particular function. Since $s$ upper bounds any other selection of $\alpha \leq s$, the technique proves NP-complete for any $|f(v)| \geq \alpha$ for this $f$ (since NP-complete for max possible $s$). Is the interpretation correct? Secondly, since the technique shows NP-completeness for this selection of function $f$, it is NP-complete for any other non-trivial function (Eg: legendre symbol, modulo primes operations, random fixed assignment etc)? Is this interpretation correct too?  
> **username_0**: Can I enlarge the set $\pm1$ to $−s_1,s_1+1,⋯−1,0,1,…,s_2−1,s_2$ with $s_1 \neq s_2$ and still preserve NP-completeness?  
> **username_3**: @Arul, the answer to your questions are: Yes (NP-completeness is about worst-case hardness, so it suffices to show that at least some instances of the problem are hard), No (not necessarily; it depends whether the reduction can be performed), Yes (you can easily adjust the reduction: simply set $f(1)=f(2)=f(3)=s_2$, $f(x)=0$ for all other $x$, and $\alpha=s\times s_2$).  
> **username_3**: @Arul, this is not a forum: if you have a different question, you should probably post a separate question with the correct set of requirements.  But before you do that, make sure you take note that this site is for research-level questions in theoretical computer science.  Make sure you have a solid understanding of NP-completeness and reductions.  Your follow-up questions make me think you might be better served by first brushing up on your knowledge in this area, or by asking some more basic questions on CS.StackExchange, rather than here which is for research-level questions.  
> **username_0**: well I am not from tcs... sorry to make this post here. was facing a problem which reduced to this in my field  

---

