# Reduce knapsack to problem with {0,1}-Matrix

I'm looking for a problem, where i can reduce the knapsack feasibility problem:

$$a^Tx=b,\ \textbf{with} \ a\in \mathbb{N}^n,b \in \mathbb{N}, x \in \{0,1\}^n$$

to a problem, where i have a matrix with only {0,1} entries. What would be a suitable problem, where there is easy reduction?

• Welcome to CS.SE! I don't understand what you are asking. What are you looking for? You are looking for any problem that involves a matrix with {0,1} entries and that is NP-complete? What do you want to do with that problem/reduction? Are you trying to prove that knapsack is NP-complete? Please edit the question to make clearer what you're looking for and what criteria the solution must meet. – D.W. Mar 13 '16 at 1:11

I think you want to prove the Knapsack Feasibility problem NP-complete by reducing an NP-complete problem to it. If that is what you want to do, then following will suffice:

PARTITION $\leq_P$ KS_FEASIBILITY

Let the PARTITION instance be $S = \{a_i\ |\ 1 \leq i \leq n\}$, with weights $w(a_i) \in N$ and total weight $B = \Sigma_n w(a_i)$.

We can reduce partition to KS_Feasibility as:

$[w(a_1) w(a_2)...w(a_n)] \begin{bmatrix} x_1\\x_2\\...\\x_n\end{bmatrix} = B/2$, $x_i \in \{0,1\}$ for $1 \leq i \leq n$.

Then PARTITION has a solution iff KS_FEASIBILITY has a solution.

Thus KS_FEASIBILITY is NP-complete.