3
$\begingroup$

It's possible that this question is trivial and I've overlooked something.

Let us impose the following constraint on the well-known PARTITION problem: in all inputs of a new problem the number of elements is fixed and equals $k$?

Does such constraint make PARTITION polynomially solvable?

P.S. There is pseudopolynomial algorithm for it with running time $\mathcal{O}(nA)$, where $A$ is the sum of the numbers in the given input. However, fixing $n$ doesn't seem to make it polynomial in $\log A$. Or am I missing something?

1 Answers 1

2

Yes. The problem becomes in $P$. The reason is that there would be a fixed number of partitions bounded by $O(2^k)$ which is a constant. You do not need the $O(nA)$ dynamic programming algorithm.

  • 0
    Of course, you're right. Thanks.2011-02-05