# $P$-Complete proof

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.

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