World's most popular travel blog for travel bloggers.

Does 'subexponential algorithm' refer to input or number of bits used to represent input?

, , No Comments
Problem Detail: 

When an algorithm is said to be subexponential - does this refer to the input N or the number of bits used to represent N? Consider the following: trial division for integer factorization (i.e. try all numbers less than $\sqrt N$) is subexponential in terms of N.

Note: here I'm using the definition of 'subexponential' to be $2^{O(n^\epsilon)}$ for some $\epsilon < 1$.

That is it takes $2^{\log_2 \sqrt N}$ steps to factor N. This is obviously subexponential in terms of N. However, in terms of the number of bits B needed to represent N this is $2^{\frac B 2}$ which is not subexponential in terms of B.

So would trial division be considered subexponential or not? Or would it be considered both depending on whether you're referring to N or B?

Asked By : C Shreve
Answered By : D.W.

It refers to the number of bits to represent N. More generally, the complexity of a problem is normally taken to be a function of the length of the input (the number of bits needed to represent the input).

Trial division is exponential: its running time is $O(N^{1/2})$, i.e., $O(2^{B/2})$ where $B=\lg N$ is the length of the input in bits. That's an exponential function (of $B$). See Are there subexponential-time algorithms for NP-complete problems?.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback