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.
Reduce the following decision problem to CNF-SAT
complexity theory;reductions;satisfiability;decision problem