Return to Answer

Suppose we have a knapsack of size $K = 10$, and items of size $x_1=4; x_2 = 5; x_3 = 6$. Clearly if $K - x_1 - x_3 = 0$, then set $A = 2K - x_1 - x_2 - x_3$ and $A - x_1 + x_2 - x_3 = 0$.

If $K$ is the size of a knapsack and $x_i$ is the weight of the $i$th item, then set $a_1 = 2K - \sum_{i} x_i$ and $a_i = x_{i-1}$. If you can determine if the expression $a_1 \pm a_2 \pm a_3 \pm \ldots$ is ever 0 you can solve the knapsack problem.

Suppose we have a knapsack of size $K = 10$, and items of size $x_1=4; x_2 = 5; x_3 = 6$. Clearly there is an exact solution to the decision version of the 0/1 knapsack problem: $K - x_1 - x_3 = 0$. If we set $A = 2K - x_1 - x_2 - x_3$, this solution gives us $A - x_1 + x_2 - x_3 = 0$.

If $K$ is the size of a knapsack and $x_i$ is the weight of the $i$th item, then set $a_1 = 2K - \sum_{i} x_i$ and $a_i = x_{i-1}$. If you can determine if the expression $a_1 \pm a_2 \pm a_3 \pm \ldots$ is ever 0 you can solve the knapsack problem. Therefore I expect there is no efficient solution.

I doubt there is an efficient algorithm. Suppose you have a knapsack of size $a_1 - \sum_{i>1} a_i$ and a collection of items each weighing $a_i/2$ for $i > 1$.

Determining if $\mathcal{L}(f_{a_1}f_{a_2}\cdots f_{a_k})$ is non-zero is equivalent to asking if there is a way to pack the knapsack exactly.

Suppose we have a knapsack of size $K = 10$, and items of size $x_1=4; x_2 = 5; x_3 = 6$. Clearly if $K - x_1 - x_3 = 0$, then set $A = 2K - x_1 - x_2 - x_3$ and $A - x_1 + x_2 - x_3 = 0$.

If $K$ is the size of a knapsack and $x_i$ is the weight of the $i$th item, then set $a_1 = 2K - \sum_{i} x_i$ and $a_i = x_{i-1}$. If you can determine if the expression $a_1 \pm a_2 \pm a_3 \pm \ldots$ is ever 0 you can solve the knapsack problem.

I doubt there is an efficient algorithm. Suppose you have a knapsack of size $\sum_{i} a_i$ and a collection of items each weighing $2a_i$ for $i > 1$.

Determining if $\mathcal{L}(f_{a_1}f_{a_2}\cdots f_{a_k})$ is non-zero is equivalent to asking if there is a way to pack the knapsack exactly.

I doubt there is an efficient algorithm. Suppose you have a knapsack of size $a_1 - \sum_{i>1} a_i$ and a collection of items each weighing $a_i/2$ for $i > 1$.

Determining if $\mathcal{L}(f_{a_1}f_{a_2}\cdots f_{a_k})$ is non-zero is equivalent to asking if there is a way to pack the knapsack exactly.