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

Theresa Archer 2022-06-29 Answered
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
You can still ask an expert for help

Want to know more about Inequalities systems and graphs?

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

Zayden Andrade
Answered 2022-06-30 Author has 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.
Did you like this example?
Subscribe for all access

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2022-06-14
Given linear system:
4 + δ 1 δ 2 0 2 δ 1 + δ 2 0 1 + δ 1 δ 2 + δ 3 0
How from there it follows that δ 2 = δ 3 = 0 and δ 1 0?
asked 2022-07-03
Let Δ be an indecomposable root system in a real inner product space E, and suppose that Φ is a simple system of roots in Δ, with respect to an ordering of E. If Φ = { α 1 , , α l }, prove that
α 1 + + α l Δ
I know that any positive root γ may be written as a sum of simple roots, and furthermore that every partial sum is itself a root, but I am unsure if that will help me or not. Any hints to get me started?
asked 2021-01-28
List all four corner points, as ordered pairs of the form ( x, y), for the following system of inequalities:
5xy20
x+3y24
x0
y0
asked 2022-06-19
find the solution of the following two inequalities for variables p and q:
p < p 2 4 q
p < p 2 4 q
asked 2022-06-22
Differential equation for a spring mass system
m y + β y + k y = 0
I have to find the displacement y at any time t. β = 2 m k and the initial conditions are y ( 0 ) = h > 0 and y ( 0 ) = v. I initally found the following
y = ( a + b t ) e t m k m
I am currently stuck with the initial conditions as I end up with b = v m k a k from y ( 0 ) = v and I don't know how to interpret y ( 0 ) = h > 0
Now have
y = ( h + v + h t k m ) e t m k m
and have to express y=0 as an inequality v < f ( h , k , m ) for the function f
asked 2022-06-09
Suppose that we have following interval (−5,2),we should find such a, which takes all possible values from this interval,creates following inequality systems
5 + a | 2 y | 0
| x | | a 2 | 2
asked 2022-05-30
how to solve for x in an inequality of this form:
a x + b < c x + d < e x + f (a, b, c, d, e, f are constants; inequality signs may be " ") I was taught that we only needed to solve a x + b < c x + d and c x + d < e x + f and not a x + b < e x + f but I do not understand why.