<p>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 <em>only</em> 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.</p>

CC BY-SA 2.5
2010-12-22T14:46:23.893Z
2010-12-22T18:14:22.870Z
2010-12-22T18:14:22.870Z
Sacha
<p>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.</p>

<p>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$.</p>

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

CC BY-SA 2.5
2010-12-23T13:57:22.383Z
2010-12-23T13:57:22.383Z
Dana Moshkovitz
<p>Garey and Johnson's <a href="http://rads.stackoverflow.com/amzn/click/0716710455" rel="nofollow">Computers and Intractability: A Guide to the Theory of NP-Completeness</a> (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. </p>

CC BY-SA 2.5
2010-12-26T02:34:32.527Z
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.
Nikhil
CC BY-SA 2.5
2010-12-22T21:42:03.237Z
2010-12-22T21:42:03.237Z
Luca Zanetti
<p>Consider the following algorithm:</p>

<p>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.</p>

<p>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?</p>

CC BY-SA 2.5
2010-12-22T13:31:04.097Z
I corrected a typo: It is $O(2^n)$, not $O(2^{\log n})$.
Sadeq Dousti
CC BY-SA 2.5
2010-12-22T13:41:12.267Z
@Sadeq: Why is that? The input is a number $n$, which has its length $\log n$.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-22T13:42:27.020Z
@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?
Nikhil
CC BY-SA 2.5
2010-12-22T14:20:08.247Z
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).
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-22T14:26:10.787Z
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.)
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-22T19:36:55.380Z
Oops! I made a mistake. I thought the input is represented in unary ($1^n$). That's a convention in cryptography. Sorry that I made a mess!
Sadeq Dousti
CC BY-SA 2.5
2010-12-26T02:33:22.700Z
@Tsuyoshi: Oops! Thanks a lot. I was not aware of this beforehand.
Nikhil
<ds.algorithms><np-hardness><big-picture><exp-time-algorithms>
Pseudo-polynomial time algorithms
Nikhil
# Pseudo-polynomial time algorithms

(Asked by: username_0 on 2010-12-22)

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?

**Tags:** ds.algorithms, np-hardness, big-picture, exp-time-algorithms
> **Comments:**
> **username_1**: I corrected a typo: It is $O(2^n)$, not $O(2^{\log n})$.  
> **username_2**: @Sadeq: Why is that? The input is a number $n$, which has its length $\log n$.  
> **username_0**: @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?  
> **username_3**: 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).  
> **username_3**: 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.)  
> **username_1**: Oops! I made a mistake. I thought the input is represented in unary ($1^n$). That's a convention in cryptography. Sorry that I made a mess!  
> **username_0**: @Tsuyoshi: Oops! Thanks a lot. I was not aware of this beforehand.  

---

## 3 answers

### Answer by username_4 on 2010-12-22. Score: 8 | Accepted answer

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.


---

### Answer by username_5 on 2010-12-23. Score: 6

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.


---

### Answer by username_6 on 2010-12-22. Score: 4

Garey and Johnson's [Computers and Intractability: A Guide to the Theory of NP-Completeness](http://rads.stackoverflow.com/amzn/click/0716710455) (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.

> **Comments:**
> **username_0**: 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.  

---

