# A max-even subset problem

I want to know if there is any polynomial algorithm for the problem, or any NP-completeness result.

• Given a set $S$ and $m$ subsets $C_1, \dots, C_m$ of $S$, we want to find a non-empty set $X\subseteq S$ such that $|X\cap C_i|$ is even for as many $i$ as possible.

We can see this problem in another way: given $m$ $\{0,1\}$-vectors of size $n$, find a vector $X$ of size $n$ that has even inner product with the greatest possible number of the vectors.

• Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. – Raphael Jun 22 '16 at 14:39
• I guess you want to find $X$ as large as possible? – Raphael Jun 22 '16 at 14:40
• i do a research on computer science and i reached to this problem and i think that it might be a famous problem, but i cant find this with search and i can't solve it myself, so i decided to post it here.no, X can be any non empty subset. the goal is to maximize the number of Ci's. – MohammadJavad Hajialikhani Jun 22 '16 at 18:54

Input: a $n \times n$ matrix $M$ of integers modulo 2
Goal: find a $n$-vector $x$ such that the Hamming weight of $Mx$ is as small as possible (with all arithmetic modulo 2)
This is the problem of finding a minimum-weight codeword for a linear code over $GF(2)$. This problem is NP-hard. See, e.g.,
There are heuristics and algorithms that improve upon brute-force search, and algorithms that can work in polynomial time for certain special cases, but in the general case this is still hard if $n$ is large.
• @MohammadJavadHajialikhani, I think it's equivalent, if we let $A$ be the parity check matrix of the code given by the generator matrix $M$. (I could be wrong.) – D.W. Jun 23 '16 at 16:52