0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    May 3, 2022 at 10:49
  • $\begingroup$ 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. $\endgroup$
    – Hiroki Morizumi
    May 3, 2022 at 22:54

0

Reset to default

Your Answer

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