-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$
  • 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 Jun 22 '16 at 14:39
  • $\begingroup$ I guess you want to find $X$ as large as possible? $\endgroup$ – Raphael Jun 22 '16 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$ – MohammadJavad Hajialikhani Jun 22 '16 at 18:54
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$
  • $\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$ – MohammadJavad Hajialikhani Jun 23 '16 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. Jun 23 '16 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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