2
$\begingroup$

I’m wondering whether there are any algorithms that use so much time that they must be represented using Knuth up-arrow notation.

Required: Use more than one up-arrow for time complexity.

Bonus points:

  • Have the algorithm be useful.

  • Have the algorithm be useful and optimized

$\endgroup$
  • $\begingroup$ If you don't mind artificial problems, there are some. For example, define sets $S_0 = \emptyset$ and $S_n = \{0, 1\}^{S_{n-1}} = \{f : S_{n-1} \rightarrow \{0, 1\}\}$. Brute force search over $S_n$ would take tetrative time. $\endgroup$ – Solomonoff's Secret Jul 12 '18 at 17:19
7
$\begingroup$

Yes! A simple automaton-based algorithm for answering first-order queries in Presburger arithmetic (and some extensions) has worst-case running time about $2 \uparrow\uparrow n$, where $n$ is the number of quantifier alternations in the query. Despite this formidable worst-case running time the algorithm has been implemented and gives useful results (see Hamoon Mousavi's implementation here).

$\endgroup$
  • $\begingroup$ Nice! This type of answer was exactly what I was looking for! I only didn’t require the usefulness parameter because I thought it may not be possible! $\endgroup$ – JavaScriptCoder Jul 13 '18 at 20:55
3
$\begingroup$

For any computable function $f$, there are trivially algorithms that run in time $\Omega(f)$:

x := f(n);
for i = 1 to x do [nothing];

If, in addition, $f$ is time-constructible, the above algorithm runs in time $\Theta(f(n))$.

I forego my bonus points, since the above is neither useful nor optimized.

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