0
$\begingroup$

I was reading some research paper where for hypergraph of bounded rank $k$ they have given moderately exponential algorithm. The runtime of the algorithm is $e^{ \mathcal {O}(k^2\sqrt n) \cdot poly(n)}$. Here $k$ is the rank of the hypergraph, and $poly(n)$ means polynomial in variable $n$.

What is the meaning of moderately exponential running time ?

I have seen this link, but did not understand much.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ It's not a precisely defined term and depends on context. $\endgroup$
    – adrianN
    Aug 26, 2017 at 8:00
  • 2
    $\begingroup$ So, moderately exponential according to the link means more than any polynomial, but less than any exponential. The runtime you mention does not fall in that definition, since the $Poly(n)$ in the exponent is too large. Perhaps "moderate" is only used informally, instead? $\endgroup$
    – chi
    Aug 26, 2017 at 9:13
  • 1
    $\begingroup$ @ adrianN In the context of isomorphism of algebraic and combinatorial structures. $\endgroup$
    – user35837
    Aug 26, 2017 at 10:00
  • 2
    $\begingroup$ @chi: If that is the runtime, then "moderately" is most likely meant as a joke. "We have this algorithm, but its runtime is so awful, you have no chance for any but the smallest n". $\endgroup$
    – gnasher729
    Aug 26, 2017 at 19:37

2 Answers 2

Reset to default
1
$\begingroup$

Moderately exponential is not a widely accepted term in general theoretical computer science, though it might have a widely accepted meaning in the area to which the paper you are citing belongs.

From context, it seems that the meaning here is $\exp O(n^\alpha)$ for $\alpha < 1$; an exponential running time would be $\exp O(n)$ or worse.

Improve this answer
$\endgroup$
2
$\begingroup$

As others have mentioned, there is no precise definition. The term is often used in the field of exact exponential-time algorithms. Here, an exponential-time algorithm that is faster than the naive algorithm can be said to be moderately exponential.

For example, the naive exponential-time algorithm for finding a maximum independent set in a graph tries all possibilities and runs in $O^*(2^n)$ time. Thus, any (exponential-time) algorithm that runs in $O^*(c^n)$ time for any $c < 2$ can be said to be moderately exponential.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.