We often hear about some algorithms' running time that is polynomial, and some algorithms' running time that is exponential. But is there an algorithm whose time complexity is between polynomial time and exponential time?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ To quote Aaronson, "In some contexts, "exponential" means $c^n$ for some constant $c>1$, but in most complexity-theoretic contexts it can also mean $c^{n^d}$ for constants $c>1$ and $d>0$". Some intermediates proposed in answers here are of the latter form for some $d\in(0,\,1)$. Could you clarify which meaning of sub-exponential you intended? $\endgroup$– J.G.Dec 23, 2021 at 12:59
-
1$\begingroup$ I think the question should be rephrased. In fact, most of the answers below are answering a different question. Making up an algorithm that takes a specific time is extremely easy and not particularly interesting. Most of the answers below focus instead on finding a problem that can be solved in subexponential time but cannot be solved in polynomial time. $\endgroup$– StefDec 24, 2021 at 11:03
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
There is a category of time complexity called quasi-polynomial. It consists of a time complexity of $2^{\mathcal{O}(\log^cn)}$, for $c> 1$. It is asymptoticaly greater than any polynomial function, but lesser than exponential time.
Another category is sub-exponential time which name speaks for itself. It is sometimes defined as $2^{o(n)}$.
The problem of graph isomorphism can be solved in sub-exponential time, but no algorithm in polynomial time is known.
answered Dec 22, 2021 at 14:12
$\begingroup$
$\endgroup$
14
The general number field sieve, the most efficient known algorithm for factoring large numbers, has a runtime that's roughly $\exp(n^{1/3})$, where $n$ is the number of digits in the number to be factored. This runtime grows with $n$ faster than any polynomial, but slower than exponential.
This class of runtimes is generally still considered "hard" for the purposes of practical computation (hence the security of RSA and other cryptography systems that depend on the difficulty of factoring). The cutoff for "practically efficient to compute" is generally taken to be right above polynomial growth, not right below exponential growth.
-
3$\begingroup$ Small add: If one can solve the factoring they can solve the RSA problem, for the reverse, there is no proof yet. So one may find a way to solve the RSA problem to access the messages without factoring. $\endgroup$– kelalakaDec 22, 2021 at 21:26
-
$\begingroup$ @kelalaka Indeed, thanks for the add. RSA does indeed depend on the hardness of factoring, but it also depends on the hardness of other tasks that might end up being easier than factoring. It’s interesting to note that the most efficient implementation of Shor’s algorithm to decrypt an RSA message doesn’t actually involve factoring any numbers. $\endgroup$– tparkerDec 22, 2021 at 22:55
-
5$\begingroup$ ‘The cutoff for "practically efficient to compute" is generally taken to be right above polynomial growth’ – well that depends a lot on the field. In many applications, the cutoff between “efficient” and “infeasibly expensive” lies between $\mathcal{O}(n\cdot\log n)$ and $\mathcal{O}(n^2)$... $\endgroup$ Dec 23, 2021 at 0:39
-
1$\begingroup$ @kelalaka Yes, Shor's quantum algorithm can be used to factor the modulus, and this one way that it can be used to decrypt an RSA-encrypted message - but it turns out that there's an even (slightly) more efficient implementation of Shor's algorithm that directly decrypts the message without ever factoring the modulus. $\endgroup$– tparkerDec 23, 2021 at 15:01
-
1$\begingroup$ @tparker in you could theoretically train a deep neural network by forward-mode automatic differentiation. That's $\mathcal{O}(n^2)$ in the number of parameters. But in practice, these networks always have so many parameters that this would be infeasible. $\endgroup$ Dec 23, 2021 at 15:43
$\begingroup$
$\endgroup$
Other answers have given some specific examples of problems whose difficulty is conjectured to be between polynomial and exponential time, but the Time Hierarchy Theorem gives a general proof that for any time-constructible function $f(n)$, there is some decision problem which can be solved in time $f(n) \cdot log^2(n)$ but not in time $f(n)$.
Namely: Given an encoding of a Turing machine $M $and an input $x$, does $M$ accept $x$ within $f(|x|)$ steps?
So taking $f(n) = 2^{\sqrt{n}}$, the problem of deciding whether an arbitrary Turing machine halts within $2^{\sqrt{n}}$ is solvable in time $ n \cdot 2^{\sqrt{n}}$, but not solvable in time less than $2^{\sqrt{n}}$.
$\begingroup$
$\endgroup$
8
Sure, eg you can easily built an algorithm taking $\Theta(2^{\sqrt{n}})$ steps, and this is slower than polynomial but faster than exponential. For this, compute $\frac{2^{\sqrt{n}}}{\sqrt{n}}$ (in binary), and then count down from there, making sure to make a full pass through the array each time.
If you just want something intermediate, you can make it even simpler and just generate an array of length $\sqrt{n}$ and count up from $00\ldots 0$ to $11\ldots 1$. This clearly takes at least $2^{\sqrt{n}}$ steps, and at most $\sqrt{n}2^{\sqrt{n}}$.
-
1$\begingroup$ Can you help give me an example of such an algorithm? $\endgroup$– lz9866Dec 22, 2021 at 13:37
-
6
-
1$\begingroup$ You've essentially just told OP "sure, it's easy". That's not much of an answer. $\endgroup$ Dec 22, 2021 at 21:59
-
1$\begingroup$ @einpoklum I find a bit more content than just "it's easy", specifically because it names an asymptotic class between the two. I personally took the question to essentially be asking if there were any such. $\endgroup$ Dec 22, 2021 at 22:20
-
$\begingroup$ @DanielWagner: One might interpret OP to not be aware of this, but - it's not what OP literally wrote. $\endgroup$ Dec 22, 2021 at 22:28