Theresa Archer

2022-06-29

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

Zayden Andrade

Beginner2022-06-30Added 22 answers

We can reduce 1-IN-3SAT 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}^{\prime}$ and add the constraint ${x}_{i}+{x}_{i}^{\prime}=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 $\mathrm{\neg}{b}_{i}$ occurs in a clause, use ${x}_{i}^{\prime}$ instead of ${x}_{i}$.

- Require that at most $n$ rational variables (out of $2n$) can be nonzero.

From the constraint ${x}_{i}+{x}_{i}^{\prime}=1$, we know that at least one of ${x}_{i}$ and ${x}_{i}^{\prime}$ has to be nonzero for every $i,$ which is already $n$ nonzero variables. That means exactly one of ${x}_{i}$ and ${x}_{i}^{\prime}$ can be nonzero, which means either ${x}_{i}=1$ and ${x}_{i}^{\prime}=0$, or ${x}_{i}=0$ and ${x}_{i}^{\prime}=1$. Interpret this as a truth assignment for ${b}_{i}$: ${x}_{i}=1\phantom{\rule{thickmathspace}{0ex}}\u27fa\phantom{\rule{thickmathspace}{0ex}}{b}_{i}$ and ${x}_{i}^{\prime}=1\phantom{\rule{thickmathspace}{0ex}}\u27fa\phantom{\rule{thickmathspace}{0ex}}\mathrm{\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.

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}^{\prime}$ and add the constraint ${x}_{i}+{x}_{i}^{\prime}=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 $\mathrm{\neg}{b}_{i}$ occurs in a clause, use ${x}_{i}^{\prime}$ instead of ${x}_{i}$.

- Require that at most $n$ rational variables (out of $2n$) can be nonzero.

From the constraint ${x}_{i}+{x}_{i}^{\prime}=1$, we know that at least one of ${x}_{i}$ and ${x}_{i}^{\prime}$ has to be nonzero for every $i,$ which is already $n$ nonzero variables. That means exactly one of ${x}_{i}$ and ${x}_{i}^{\prime}$ can be nonzero, which means either ${x}_{i}=1$ and ${x}_{i}^{\prime}=0$, or ${x}_{i}=0$ and ${x}_{i}^{\prime}=1$. Interpret this as a truth assignment for ${b}_{i}$: ${x}_{i}=1\phantom{\rule{thickmathspace}{0ex}}\u27fa\phantom{\rule{thickmathspace}{0ex}}{b}_{i}$ and ${x}_{i}^{\prime}=1\phantom{\rule{thickmathspace}{0ex}}\u27fa\phantom{\rule{thickmathspace}{0ex}}\mathrm{\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.

Find the volume V of the described solid S

A cap of a sphere with radius r and height h.

V=??

Whether each of these functions is a bijection from R to R.

a) $f(x)=-3x+4$

b) $f\left(x\right)=-3{x}^{2}+7$

c) $f(x)=\frac{x+1}{x+2}$

?

$d)f\left(x\right)={x}^{5}+1$In how many different orders can five runners finish a race if no ties are allowed???

State which of the following are linear functions?

a.$f(x)=3$

b.$g(x)=5-2x$

c.$h\left(x\right)=\frac{2}{x}+3$

d.$t(x)=5(x-2)$ Three ounces of cinnamon costs $2.40. If there are 16 ounces in 1 pound, how much does cinnamon cost per pound?

A square is also a

A)Rhombus;

B)Parallelogram;

C)Kite;

D)none of theseWhat is the order of the numbers from least to greatest.

$A=1.5\times {10}^{3}$,

$B=1.4\times {10}^{-1}$,

$C=2\times {10}^{3}$,

$D=1.4\times {10}^{-2}$Write the numerical value of $1.75\times {10}^{-3}$

Solve for y. 2y - 3 = 9

A)5;

B)4;

C)6;

D)3How to graph $y=\frac{1}{2}x-1$?

How to graph $y=2x+1$ using a table?

simplify $\sqrt{257}$

How to find the vertex of the parabola by completing the square ${x}^{2}-6x+8=y$?

There are 60 minutes in an hour. How many minutes are there in a day (24 hours)?

Write 18 thousand in scientific notation.