patternMajor
Is there an algorithm whose time complexity is between polynomial time and exponential time？
Viewed 0 times
whosepolynomialexponentialtimealgorithmbetweenandtherecomplexity
Problem
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?
But is there an algorithm whose time complexity is between polynomial time and exponential time?
Solution
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.
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.
Context
StackExchange Computer Science Q#147873, answer score: 27
Revisions (0)
No revisions yet.