4
$\begingroup$

Consider the counting knapsack problem $\mathsf{\#IDKNAP}$ :

Input: $n \in \mathbb{Z_+}$, $s \in \mathbb{Q}_+$, where $s$ is represented by a fraction $\frac{p}{q}$ in its lowest terms.

Output: the number of 0-1 solutions (i.e. those having $s_i\in \{0,1\}$) to $s_1 + s_2 + \dots + s_n \leq s$.

What is the counting complexity of $\mathsf{\#IDKNAP}$?

Let $k := \lfloor s \rfloor$. The problem asks for the number of $n$-bit vectors with at most $k$ bits set to $1$. The solution is $\sum \limits_{i=0}^k \binom{n}{i}$, for which there is no closed form in general, and thus cannot be computed in polynomial time in the input size.

So (I think) $\mathsf{\#IDKNAP}$ would be either $\mathsf{NP~Hard}$ or $\mathsf{\#P~Hard}$. It seems to be insufficiently general to encode arbitrary $\#\mathsf{KNAPSACK}$ problems, which are $\mathsf{\#P~Hard}$. On the other hand, $\mathsf{\#IDKNAP}$ has exponentially less input size than general knapsacks, for which the weight vector $(w_1,\ldots,w_n)$ has at least $n$ bits.

$\endgroup$
  • $\begingroup$ Note that NP-hard is a property of decision problems. Your function is a bit strange since its output size is not polynomial in its input size. $\endgroup$ – Yuval Filmus Oct 12 '15 at 11:55
  • 1
    $\begingroup$ I think there's a confusion in your question: the fact that there is "no closed form" for the sum doesn't mean there is no polynomial-time algorithm to compute the sum. $\endgroup$ – D.W. Oct 12 '15 at 22:49
2
$\begingroup$

There are almost-matching lower and upper bounds for the running time of the best algorithm for this problem, considered as a function of $n$. In particular, we can prove that the complexity is $\Omega(n)$ and $O(\text{poly}(n))$, when considered only as a function of $n$.

For the upper bound, there's an algorithm whose running time is polynomial in $n$. Without loss of generality we can take $k \le n$ (for terms where $i>n$ contribute nothing to the sum). Also you can compute ${n \choose i}$ in time polynomial in $n$. Therefore, the whole sum can be evaluated in time polynomial in $n$. In other words, it's solvable in pseudo-polytime.

The size of the output can be as large as $2^n$ (e.g., where $k=n$), so the output can take $\Theta(n)$ bits to represent. This is exponential in the size of the input. Thus, any algorithm for the problem must have worst-case running time at least $\Omega(n)$.

$\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.