# Reduce the following decision problem to CNF-SAT

Input:

• $X$ = {$x_1$,$x_2$,$x_3$,...,$x_n$}

• $Y$ = {$y_1$,$y_2$,$y_3$,...,$y_m$}

• $k$, where, $k$ $\leq$ $m$

Output (Yes/No): Satisfying the following condition, can all the elements in set $X$ be assigned to elements in set $Y$, such that, no elements in $X$ is left unassigned?

Condition: At least $k$ elements in $Y$ is needed to access all the elements in $X$. All the elements assigned to $y_i \in Y$ are said to be accessible using $y_i$.

Reduce this decision problem to CNF-SAT.

Thoughts:

I have considered $n \times m$ no. of variables. Each variables for a pair of element of set $X$ and set $Y$. i.e., $a_{ij}$ : for all $x_i$ and $y_j$.

For ensuring that no elements in $X$ is left unassigned the CNF expression will be. $(a_{11} \vee a_{12} \vee ... \vee a_{1m}) \wedge (a_{21} \vee a_{22} \vee ... \vee a_{2m})... (a_{n1} \vee a_{n2} \vee ... \vee a_{nm})$

I am not able to form the CNF expression for ensuring that at least $k$ elements from $Y$ are required to access all the elements in $X$. It seems that there will be an exponential number of clauses in the expression.

Thanks for helping.

• Welcome to Computer Science! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed and/or downvoted. You may also want to check out our reference questions, or use the search engine of this site to find similar questions that were already answered. – Raphael Aug 10 '16 at 7:26
• @Raphael - Thanks for your suggestions. I have edited the details of the question as suggested. – Gradient Aug 10 '16 at 10:04