3
$\begingroup$

Consider the following algorithm:

Given a natural number as input, say $N$, the algorithm runs a loop (in which the algorithm does $O(1)$ time operations) $N$ times. Now, by definition of time complexity, we want to measure the running time as a function of input size, so the complexity of this algorithm is $O(N)=O(2^{\lg N})$. I have always felt a little uneasy that this simple algorithm is actually has an exponential running time.

More examples of such problems include integer factorization, knapsack (and a lot of other related papers Google throws up) which all have a running time that is pseudo-polynomial in the size of the input(also called as weakly NP-complete problems). Is there any survey/book that treats these problems in detail? Are there any interesting aspects of these problems (as in, they have some properties that characterize them distinctly from strongly NP-complete problems) that are well-known?

$\endgroup$
  • $\begingroup$ I corrected a typo: It is $O(2^n)$, not $O(2^{\log n})$. $\endgroup$ – M.S. Dousti Dec 22 '10 at 13:31
  • 1
    $\begingroup$ @Sadeq: Why is that? The input is a number $n$, which has its length $\log n$. $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 22 '10 at 13:41
  • 1
    $\begingroup$ @sadeq: You need log $n$ bits to represent $n$, and the algorithm runs in $n = 2^{log_2 n}$ steps, which makes it exponential in the size of the input. Or am I missing something here? $\endgroup$ – Nikhil Dec 22 '10 at 13:42
  • $\begingroup$ Nikhil, you are right. I reverted the edit and replaced small n by capital N to avoid possible confusions. Small n is certainly often used to represent the input length (not always, though). $\endgroup$ – Tsuyoshi Ito Dec 22 '10 at 14:20
  • 1
    $\begingroup$ Problems having pseudo-polynomial-time algorithms and weakly NP-complete problems are two different notions. Factoring is not known to be (weakly) NP-hard, and it is not (weakly) NP-hard unless NP=coNP. (I put “weakly” in parenthesis because when people talk about the complexity of factoring, the input size is always the number of bits, so “weakly” is redundant although technically correct.) $\endgroup$ – Tsuyoshi Ito Dec 22 '10 at 14:26
8
$\begingroup$

I think this somehow “uneasy feeling” comes from the fact that human beings consider natural numbers only with a semantic—if I see 2001, e.g., I immediately think of 9/11 or Stanley Kubrick or something, that is, you interpret the number. In terms of inputs for an algorithm, however, it is merely a string of characters, and could just as well be such nonsense as ¨*^! or anything. What we as algorithm analyzers care about is only the length of the string, and absolutely not what it contains or represents. You really have to get this into your mind because otherwise you could e.g. say that $PRIMES$ is obviously in $\mathsf{P}$ as you can just try to divide a number $x$ by all numbers between 1 and $x,$ and this algorithm has obviously polynomial runtime. I hope you see the pitfall.

$\endgroup$
6
$\begingroup$

As was already answered, measuring the running time with respect to the bit representation simply means that you refer to the number as an array of bits, and the size of the input is the length of that array.

This is the convention, but it's not necessary to measure things this way. You could say (and it's often done in complexity and crypto) that the input is $1^N$, i.e., the unary representation of the number. Then, the running time is measured with respect to N and not to $\log N$.

It all depends on the context and what's right for your particular problem.

$\endgroup$
4
$\begingroup$

Garey and Johnson's Computers and Intractability: A Guide to the Theory of NP-Completeness (chapter 4.2) provides a few pages about this argument. It's a standard text absolutely worth of reading if you haven't done it yet.

$\endgroup$
  • $\begingroup$ I have been reading Garey and Johnson's book, and that's where I got thinking about this topic. Since it is pretty old, I wanted to know if there has been any more progress around these problems. $\endgroup$ – Nikhil Dec 26 '10 at 2:34

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.