Let $RLS(k)$ be the problem where we try to determine whether a Linear System of $n$ unknown variables and $m$ equations with Rational coefficients, has a $k$-solution which is basically a vector $x=({x}_{1},{x}_{2},\dots ,{x}_{n})$ such that at most $k$ of the ${x}_{i}$'s are non-zero.

Prove that $RLS(k)$ is NP-hard

Prove that $RLS(k)$ is NP-hard