# On the proof of NP-Hardness of the Cardinality Constrained Quadratic Knapsack Problem

in Polyhedral Study of the Cardinality Constrained Knapsack Problem the authors prove that the Cardinality Constrained Knapsack Problem is NP-Hard by reducing PARTITION to it.

Besides, it's easy to see that the KP problem is a special case of the QKP.

How should one proceed to prove the NP-Hardness of the Cardinality Constrained Quadratic Knapsack Problem?

CCQKP:

$$max\ \sum_{i=1}^{n} \sum_{j=1}^{n} x_i x_j c_{ij}$$ $$s.t$$ $$\sum_{j=1}^{n} a_j x_j \leq C$$ $$\sum_{j=1}^{n}x_j = 1$$ $$0 \leq x_j \leq 1,\ j = 1,...,n$$ $$\sum_{j=1}^{n}z_j = k$$ $$z_j \in \{0,1\},\ j = 1,...,n$$

I'm aware that we usually talk about the hardness of Decision Problems even tough I'm formalizing the Optimization version of it.

• Is there anything to do? The decision problem directly reduces to the optimization problem: if you want to know "Is there a widget with weight at least $w$?" you can just compute the maximum weight of any widget and answer "yes" if that is at least $w$. – David Richerby Oct 2 '18 at 14:57
• I understand that the decision problem reduces to the optimization problem. What I'm rather interested in is how I can prove the hardness of the CCQKP. I'm sorry if the question is vague. – Rule184 Oct 2 '18 at 15:53
• When we say that an optimization problem is NP-hard, we really mean that its decision version is NP-hard. For a maximization problem, the decision version gets an instance and a value $\theta$, and the goal is to decide whether there is a feasible solution of value at least $\theta$. – Yuval Filmus Oct 2 '18 at 16:26
• @YuvalFilmus sure, I understand that. What I'm asking, though, is how I can prove that the CCQKP is NP-Hard given that both the CCKP and the QKP are NP-Hard. – Rule184 Oct 2 '18 at 22:40
• If QKP is NP-hard then so is your problem - just don’t use any cardinality constraints. – Yuval Filmus Oct 2 '18 at 22:55