A max-even subset problem

Question

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.

Answer 1

Your problem is:

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

Elwyn R. Berlekamp, Robert J. McEliece, and Henk C. A. van Tilborg. On the Inherent Intractability of Certain Coding Problems. IEEE Transactions on Information Theory 24 (1978), 384–386.

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.