1
$\begingroup$

I am reading a proof that the Subset Sum decision problem is NP-complete.

I know that the time complexity is always calculated based on the number of bits of the input in binary, hence the $\log{W}$. Also, for this specific problem the size/length of the input is $(n+1)\log{W}$, with $n$ and $W$ being two integer variables ($n$ is the number of available elements in the set and $W$ is the sum we are seeking).

However I am having some trouble when trying to understand the terminology be linear/polynomial in the input size, specifically with these two lines:

The input length is (n + 1) log W, and the running time of O(nW) is not polynomial in this input length.

and

takes O(n log W) time, linear in the input size.

How can I mathematically prove the above two lines? Or what is the mathematical reasoning behind those two statements?

I don't have this conceptual problem when there is only one variable. For example, let's say I have an algorithm with a complexity of $O(x)$ and an input size of $\log_2{x}$. Then, I can express $x$ in terms of the problem size like this: $O(2^{size})$. Now, I can see that the complexity is exponential in the size (in bits) of the problem.

But I don't know how to do this when there are two or more variables in the complexity function (in this case $W$ and $n$).

$\endgroup$
1
$\begingroup$

Suppose that the function $\ell$ represents the input length of an algorithm, in terms of several parameters $\vec{x}$, and suppose that the function $T$ represents its running time, in terms of the same parameters $\vec{x}$. Furthermore, there is a collection of valid parameter settings.

We say that $T$ is linear in $\ell$ if there exist $M,C$ such that for any valid parameter setting $\vec{x}$, if $\ell(\vec{x}) \ge M$ then $T(\vec{x}) \leq C \ell(\vec{x})$.

Similarly, we say that $T$ is polynomial in $\ell$ if there exist $M,C$ such that for any valid parameter setting $\vec{x}$, if $\ell(\vec{x}) \ge M$ then $T(\vec{x}) \leq C\ell(\vec{x})^C$.

(We get these definitions from the usual definitions of time complexity.)

In your case, $\ell$ and $T$ depend on two parameters $n,W$, and $\ell(n,W) = (n+1)\log W$. A parameter setting is valid if $n \geq 1$ and $W \geq 2$ (this unstated assumption is needed to guarantee that your running times are positive). You are interested in two functions $T$: $T_1(n,W) = nW$ and $T_2(n,W) = n\log W$.

Let us start with the second function $T_2$. For any valid $n,W$ we have $n+1 \leq 2n$ and so $\ell(n,W) \leq 2T_2(n,W)$. Therefore $T_2$ is linear in $\ell$, with $M = 1$ and $C = 2$.

Now let us consider the first function $T_1$. Suppose that $T_1$ were polynomial in $\ell$, with parameters $M,C$. Thus if $n \geq 1$, $W \geq 2$, and $(n+1)\log W \geq M$, then $nW \leq C[(n+1)\log W]^C$. In particular, taking $n=1$, we get that for any $W \geq 2$, $W \leq C2^C(\log W)^C$. Equivalently, $W = O(\log^C W)$. However, this is clearly false. Therefore $T_1$ is not polynomial in $\ell$.

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