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

I am trying to reduce Vertex Cover ($VC$) to $RLS(k)$.

My idea was that starting with a graph $G(V,E)$ then one can encode each edge $(x_i, x_j)$ as $x_i + x_j \neq 0$. Reason being, if $x_i = 0$ we want $x_j \neq 0$ (i.e. if we don't "choose" vertex i for our VC then we are forced to "choose" node j for the $VC$).

We conclude, that this System has a $k$-solution iff $G$ has a Vertex Cover of size $\leq k$

Of course, the issue is that the above is NOT a system of equations but rather a system of inequalities.

I also thought about introducing dummy variables but that didn't me lead anywhere either.

Is this even the correct reduction for this type of problem? Are there any other common reductions that could potentially be straightforward? My intuition tells me that (due to the $k$-restriction) Vertex Cover and Independent Set are probably the easiest ones. Thoughts?

Update/Note: I am quite comfortable with this topic, so I am looking for some brainstorming with a fruitful discussion, and not necessarily a solution. So don't be afraid to share even "partial" ideas.

  • $\begingroup$ So your question about whether we have k-solution or not or you want to know the k-solutions of this linear equations, I mean Is your question a counting problem or optimization problem? Also, I am not sure I've seen problems similar to your problems and there is cases where there is no algorithm to solve problems like that. $\endgroup$ – YOUSEFY Apr 10 '17 at 17:46
  • $\begingroup$ This is a complexity problem that uses reduction ideas to compare "relative" complexity. Simply put, we are trying to find which problem is harder to solve. In particular, here we are trying to prove that $RLS(k)$ is harder than some of the hardest problems in a group of "efficiently (positive) verifiable" (NP) problems called NP-complete. If you want to know more, I would start here: en.wikipedia.org/wiki/Reduction_(complexity) and here en.wikipedia.org/wiki/NP-completeness $\endgroup$ – Pellenthor Apr 10 '17 at 19:30

We can reduce 1-IN-3SAT (that is, 3SAT with the condition that in each clause, exactly one literal is true) to $RLS(k)$ as follows:

Suppose that we have a 1-IN-3SAT formula in $n$ variables $\{b_1, \dots, b_n\}$.

  • For each boolean variable $b_i$, define two rational variables $x_i$ and $x_i'$ and add the constraint $x_i + x_i' = 1$.
  • For a clause with positive literals $\{b_i, b_j, b_k\}$, add the constraint $x_i + x_j + x_k =1$.
  • When a negative literal $\neg b_i$ occurs in a clause, use $x_i'$ instead of $x_i$.
  • Require that at most $n$ rational variables (out of $2n$) can be nonzero.

From the constraint $x_i + x_i' = 1$, we know that at least one of $x_i$ and $x_i'$ has to be nonzero for every $i,$ which is already $n$ nonzero variables. That means exactly one of $x_i$ and $x_i'$ can be nonzero, which means either $x_i = 1$ and $x_i' = 0$, or $x_i = 0$ and $x_i' = 1$. Interpret this as a truth assignment for $b_i$: $x_i = 1 \; \Longleftrightarrow \; b_i$ and $x_i' = 1 \; \Longleftrightarrow \; \neg b_i$. Then the constraint we use for each clause is equivalent to saying that exactly one literal in the clause is true.

Therefore a solution to the rational linear system produces a satisfying assignment to the 1-IN-3SAT formula.

| cite | improve this answer | |
  • $\begingroup$ This is an excellent argument, thanks! For those new to the subject, it leverages the $n$-restriction beautifully in that it forces ALL the variables to be exactly 0 or 1, which is a really powerful restriction. One that can lead to many interesting reductions. $\endgroup$ – Pellenthor Apr 10 '17 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.