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

Theresa Archer

Theresa Archer

Answered question

2022-06-29

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

Answer & Explanation

Zayden Andrade

Zayden Andrade

Beginner2022-06-30Added 22 answers

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.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?