Let R L S ( 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 , … , x n ) such that at most k of the x i 's are non-zero.Prove that R L S ( k ) is NP-hard

Question

Let   R  L  S  (  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    ,  …  ,      x    n    ) such that at most   k of the       x    i  &#039;s are non-zero.Prove that   R  L  S  (  k  ) is NP-hard

Zayden Andrade · Accepted Answer

We can reduce 1-IN-3SAT to   R  L  S  (  k  ) as follows:Suppose that we have a 1-IN-3SAT formula in   n variables   {      b    1    ,  …  ,      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   ¬      b    i   occurs in a clause, use       x    i    ′   instead of       x    i  .- Require that at most   n rational variables (out of   2  n) 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    ⟺        b    i   and       x    i    ′    =  1    ⟺    ¬      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.

Let R L S ( k ) be the problem where we try to determine whether a Linear Syste

Answered question

Answer & Explanation

New Questions in Algebra I