Suppose you have a set of binary strings of length n, the magnitude of a string is the number of 1's it has. and you want the program to return true if there is a string of length n that has a magnitude of <= k and there is a index i for every y in the set string[i] = y[i] = 1 for all strings.

Example for n = 5, k = 3:

0 1 0 0 1

1 0 0 1 0

0 0 1 0 0

1 0 1 0 0

0 1 0 1 0

1 1 1 0 0 would be a solution to the above set.

  • $\begingroup$ I suspect that you have misstated your problem. Check my answer and update your question accordingly. $\endgroup$ – Yuval Filmus Mar 20 '14 at 17:57
  • $\begingroup$ You are right its fixed $\endgroup$ – RandomGuy Mar 20 '14 at 19:03
  • 1
    $\begingroup$ Your description is still very hard to understand, but your problem seems to be the same as set cover. Check my updated answer. $\endgroup$ – Yuval Filmus Mar 20 '14 at 23:04

Let me restate your problem: given a collection $S_1,\ldots,S_m \subseteq [n]$, the problem is to decide whether there is a set $S \subseteq [n]$ of magnitude at most $k$ that "hits" every set $S_i$, i.e., $S_i \cap S \neq \emptyset$. This is the same as the classical problem set cover, which is known to be NP-complete. The corresponding set cover instance has $n$ sets over the ground set $[m]$, the $i$th set being $T_i = \{ j \in [m] : i \in S_j \}$. A set cover is the same as a choice of $S$.

(Answer to old version:) Your problem is in P. If $k = 0$ then the answer is always NO. If $k \geq 1$ then the answer is YES if and only if when you write your strings as rows in a matrix, then there is a column which consists only of $1$s. This is a condition which you can check in linear time (in the input size).

  • 2
    $\begingroup$ Or just AND the strings together: there's a position that's 1 in all strings iff the AND contains a 1. $\endgroup$ – David Richerby Mar 20 '14 at 21:45
  • $\begingroup$ Correct that is my problem $\endgroup$ – RandomGuy Mar 21 '14 at 0:02

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