- INSTANCE:
Integer -matrix
,
integer
*m*-vector . - SOLUTION:
A rational
*n*-vector such that*Ax=b*. - MEASURE:
The number of non-zero elements in
*x*.

*Bad News:*Not in APX [17].*Comment:*Not approximable within for any unless NPQP [17]. The above nonapproximability results are still true for the variation in which the solutions are restricted by instead of*Ax=b*. Variation in which the solution vector is restricted to contain binary numbers is NPO PB-complete and is not approximable within for any [17]. The complementary maximization problem, where the number of zero elements in the solution is to be maximized, and the solution vector is restricted to contain binary numbers, is NPO PB-complete and is not approximable within for any [285].*Garey and Johnson:*MP5