Suppose I have a variant of the knapsack problem:

$$\max_{x} \sum_{i=1}^n v_ix_i$$

$$(\sum_{i=1}^n w_ix_i - W)^2 \leq k$$

for $$v_i, w_i \in \mathbb{R}$$, $$x_i \in \{0,1\}$$ and $$k \in \mathbb{R}, k > 0$$.

Is it known if the decision problem $$\sum_{i=1}^n v_ix_i > V$$ for some $$V$$ is NP-Complete?

The problem is clearly in $$\mathsf{NP}$$. You can see that it is $$\mathsf{NP}$$-hard by a reduction from subset sum: given a set $$X = \{ x_1, \dots, x_m \}$$ of positive integers and another integer $$T>0$$, is there a subset $$S$$ of $$X$$ such that $$\sum_{x \in S} x = T$$?
To reduce to your version of subset sum, create $$n=m$$ items, where the $$i$$-th item has value $$v_i = 1$$ and weight $$w_i=2x_i$$, and set $$W=2T$$, $$k=1$$, $$V=0$$. There is a solution to this "knapsack" instance if and only if there is a solution to the subset sum problem.
• I see. Though I'm specifying $k > 0$, it sounds like you can make all $w$ and $W$'s integer and then choose $k < 1$. Seems like I need stronger conditions on $k$... May 9, 2022 at 17:38
• I slightly modified the reduction to ensure $k>0$. May 9, 2022 at 22:14