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.

$\endgroup$
  • 1
    $\begingroup$ It's not a precisely defined term and depends on context. $\endgroup$ – adrianN Aug 26 '17 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 '17 at 9:13
  • 1
    $\begingroup$ @ adrianN In the context of isomorphism of algebraic and combinatorial structures. $\endgroup$ – aaag Aug 26 '17 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 '17 at 19:37
2
$\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.

$\endgroup$
1
$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.