NP Completeness of System of Linear Inequalities

MISTAKES:
- DO NOT TRY TO SHOW THAT ANY PROBLEM IN NP is reducible to the problem in question. I meant to say "show that any problem which is known to be NP-Complete is reducible". My bad.

[NoticedByYou]

Here are the values of x1, x2, ...xn in the inequalities restricted to 0 or 1? If not I do not see how a solution for the linear inequalities can necessarily be translated to a solution of 3SAT. Could you clarify on this point?

[muldvarp]

I have come across this since I want to show inclusion in NP of a problem that can be reduced to this. Unfortunately, your argument for inclusion in NP is not sufficient, though. You say that, given values for x, one can obviously check in polynomial time whether A x <= b holds. This is clearly possible in time polynomial in |A|, |b| and |x|. But with this argument, any recursively enumerable problem would be in NP!

For true inclusion in NP you need something stronger: this has to be possible in time polynomial in the size of the input to the original problem, i.e. polynomial in |A| and |b| only! Equivalently, you would have to show that one can always find a witnessing solution x of size polynomial in |A|+|b|. Is there any striking argument for that?

[iliaslolis]

Why didn't you reduce the Hamiltonian Path to Linear Inequalities since it is easier?