-1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – D.W. Mar 13 '16 at 1:11
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.