<p>My main interest is complexity theory, and I'm studying the large or huge advice of Turing machines in the ongoing work.<br />
As related to the study, I'm wondering what's known about &quot;precomputation&quot; in algorithms for the following cases. I'm most interested in the following framework.</p>
<p><strong>An example to explain the framework:</strong> MergeSort runs in <span class="math-container">$O(n \log\log n)$</span> time if <span class="math-container">$n$</span> is fixed and precomputed data of <span class="math-container">$\tilde{O}(k^{\frac{n}{\log n}})$</span> space are given.<br />
(Assume that the items to sort are integers in the set <span class="math-container">$\{1, 2, \ldots, k\}$</span>.) (We execute the <span class="math-container">$\log\log n$</span> ordinary recursive steps of MergeSort, and sort <span class="math-container">$\frac{n}{\log n}$</span> items by precomputed data which have all patterns. )</p>
<p>Thus, MergeSort can be speeded up from <span class="math-container">$O(n \log n)$</span> time to <span class="math-container">$O(n \log\log n)$</span> time by huge precomputed data.</p>
<p><strong>Question:</strong> What's known about the similar approach for NP-hard problems?</p>

CC BY-SA 4.0
2022-05-03T10:49:19.337Z
Well, if you allow yourself exponential space as in your MergeSort example (which I suppose means that you are using a RAM model where you can address such a large memory efficiently), you can compute *any* decision problem in time $n+1$ by just precomputing all the answers. I don’t see what’s the point of all this.
Emil Jeřábek
CC BY-SA 4.0
2022-05-03T22:54:04.337Z
Precomputed data can be beyond polynomial size, but it's hoped to small as soon as possible. One of situations which I think is that precomputed data are in some places of the internet and anyone can use it as public data. Although I'm not familiar with practical application study, I have guessed that the data in the internet can be huge, at least beyond polynomial size.
Hiroki Morizumi
<ds.algorithms><reference-request><big-picture>
Algorithms with advices of huge precomputed data
Hiroki Morizumi
# Algorithms with advices of huge precomputed data

(Asked by: username_0 on 2022-05-02)

My main interest is complexity theory, and I'm studying the large or huge advice of Turing machines in the ongoing work.  
As related to the study, I'm wondering what's known about "precomputation" in algorithms for the following cases. I'm most interested in the following framework.

**An example to explain the framework:** MergeSort runs in $O(n \log\log n)$ time if $n$ is fixed and precomputed data of $\tilde{O}(k^{\frac{n}{\log n}})$ space are given.  
(Assume that the items to sort are integers in the set $\{1, 2, \ldots, k\}$.) (We execute the $\log\log n$ ordinary recursive steps of MergeSort, and sort $\frac{n}{\log n}$ items by precomputed data which have all patterns. )

Thus, MergeSort can be speeded up from $O(n \log n)$ time to $O(n \log\log n)$ time by huge precomputed data.

**Question:** What's known about the similar approach for NP-hard problems?

**Tags:** ds.algorithms, reference-request, big-picture
> **Comments:**
> **username_1**: Well, if you allow yourself exponential space as in your MergeSort example (which I suppose means that you are using a RAM model where you can address such a large memory efficiently), you can compute *any* decision problem in time $n+1$ by just precomputing all the answers. I don’t see what’s the point of all this.  
> **username_0**: Precomputed data can be beyond polynomial size, but it's hoped to small as soon as possible. One of situations which I think is that precomputed data are in some places of the internet and anyone can use it as public data. Although I'm not familiar with practical application study, I have guessed that the data in the internet can be huge, at least beyond polynomial size.  

---

## 0 answers

