# SAT reduction to prove NP completeness [closed]

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.

• I suspect that you have misstated your problem. Check my answer and update your question accordingly. – Yuval Filmus Mar 20 '14 at 17:57
• You are right its fixed – RandomGuy Mar 20 '14 at 19:03
• Your description is still very hard to understand, but your problem seems to be the same as set cover. Check my updated answer. – 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).