I was trying to solve problem from Cormen page 1100 34.5-2
Given an integer $m * n$ matrix A and an integer $m$-vector $b$, the 0-1 integer- programming problem asks whether there exists an integer $n$-vector $x$ with elements in the set $<0, 1>$ such that $Ax\leq b$. Prove that 0-1 integer programming is NP-complete. (Hint: Reduce from 3-CNF-SAT.)
I do not understand what is 0-1 integer programming problem and what m and n vector mean here... Like what $Ax\leq b$ means.
Here is solution (I will really appreciate if you can explain me this one..):
Your $k$-vectors are just vectors with $k$ elements. The IntProg problem is defined by $$(A,b) \in \mathrm{IntProg} \\ \Leftrightarrow \exists x\in \{0,1\}^n : (Ax)_i \le b_i \forall 1\le i \le m$$ Where $A\in \mathbb R^{m\times n}$ and $b\in\mathbb R^m$. The RHS of the condition is abbreviated to $Ax \le b$ wich is to be read as "component-wise less than or equal to".
Intuitively IntProg asks if there is a subset of the columns of $A$ such that their sum ($Ax$ sums all the $i$-th columns where $x_i = 1$) is component-wise less than or equal to $b$.
For example $A = (3\ -1\ 2)$ and $b=-1$ is a yes-instance because the choice $x = (0\ 1\ 0)^T$ gives $Ax = -1 \le b$.
If you want to know what a vector and a matrix is, you should consult wikipedia or google.