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

## closed as unclear what you're asking by D.W.♦, Juho, David Richerby, vonbrand, Rick DeckerMar 24 '14 at 18:48

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• 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).