-1
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – Raphael
    Commented Jun 22, 2016 at 14:39
  • $\begingroup$ I guess you want to find $X$ as large as possible? $\endgroup$
    – Raphael
    Commented Jun 22, 2016 at 14:40
  • $\begingroup$ 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. $\endgroup$ Commented Jun 22, 2016 at 18:54

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ thank you for answer. are you sure that this problem is exactly the problem that paper discusses about? i think that is another problem, wants to minimize the weight of x such that xA=0, for given A. is there any reduction ? $\endgroup$ Commented Jun 23, 2016 at 8:01
  • $\begingroup$ @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.) $\endgroup$
    – D.W.
    Commented Jun 23, 2016 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.