I need to solve the next problem: Consider the language:

$$\operatorname{LIN\mbox{−}PROG} = \left\{(A, b)\bigg|\begin{gather} \exists\in\mathbb{R}^n\ Ax\leq b\text{ where }A\in\mathbb{R}^{m\times n}\ b\in\mathbb{R}^m\\\text{ and } Ax\leq b\text{ means } \forall i.(Ax)_i\leq b_i\end{gather}\right\}$$

Prove that $\operatorname{LIN\mbox{−}PROG}$ is $P$-Hard with respect to log-space reductions.

Remark: It is known that $\operatorname{LIN\mbox{−}PROG}\in P$ hence it is $P$-Complete.

I've been trying for hours to think of a reduction that would work.

My direction is as follows:

Take out as output the calculation table of $M$ on $x$, because I know that if $M$ accepts $x$, the last row (due to convention) should be 1 followed by zeros, but I get confused because the table itself only describes the calculation and does not do the calculation itself, so my idea not entirely accurate. Assuming I can somehow realize the above idea, the reduction will be correct because I will choose vector $b$ to be a negative number followed by zeros, and the only way to have a ​​solution $x$ to the equation is if the last configuration is accepting one, since if the first row in the calculation table is zeros only, for every vector $x$ the first entry of $Ax$ is $0$, and will never be less than a negative number.

  • 1
    $\begingroup$ What are you trying to reduce from? $\endgroup$ – D.W. Nov 17 '20 at 18:08

Your Answer

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

Browse other questions tagged or ask your own question.