Is finding a single digit of a computation is as hard as finding the computation?

Question

Let $f: \mathbb{N} \rightarrow \mathbb{N}$ a computable function such that computing $f(n)$ takes $\Omega(2^{2^{2^{|n|}}})$ time in worst case terms and such that the languages:

$$\begin{align*} L_1 &= \{ n \mid f(|n|) = n \} \\ L_2 &= \{ (n,k) \mid \text{the first digit of $n$ is the $k$'th digit of $f(|n|)$} \}\end{align*}$$

Are infinite.

Prove or disprove that $L_1 \leq_{P} L_2$ i.e there is a polynomial time reduction from $L_1$ to $L_2$.

Heuristically I am thinking that for any function it is impossible to compute a digit of the computation without generally computing the function so I am thinking it should be correct, though not sure how to prove it formally.

Answer 1

For some functions $f$ you might be correct. For example, we can arrange that $f(|n|) \neq n$ for all $n$ (by controlling the length of $f(x)$) while keeping $f$ arbitrarily difficult, and so $L_1$ reduces to $L_2$ trivially.

Here is a function $f$ satisfying your constraint, for which $L_1$ does not polynomially reduce to $L_2$. The construction uses diagonalization. (There is some ambiguity in your notation, but the proof can be adapted however you resolve the ambiguities.)

Let $L$ be some computable language which requires time $2^{2^{2^n}}$ (such languages exist due to the time hierarchy theorem). We define the function $f$ as follows: $f(\epsilon) = f(0) = 0$, and $f(0x)$ is the indicator of $x \in L$. We define the rest of the function $f$ by giving an algorithm which eventually defines all remaining values.

Let $\phi_i$ be an enumeration of all functions computable in polynomial time. We can construct such an enumeration using timed Turing machines. We go over the functions $\phi_i$ in order. When it's time to process $\phi_i$, let $n \geq 1$ be the smallest value on which $f$ is undefined. Let $m = \phi_i(0^n,2)$. We consider several different cases:

• Case 1: $f(|m|)$ is already defined. If the second digit of $f(|m|)$ is $0$, define $f(n) = 1^n$, otherwise define $f(n) = 0^n$.
• Case 2: $f(|m|)$ is not defined, and $|m| \neq n$. Define $f(|m|)$ arbitrarily, and proceed as in case 1.
• Case 3: $|m| = n$. Set $f(n) = 10$.

In all cases, we ensure that $f(n) \neq 0^n$ iff the first digit of $0^n$ equals the second digit of $f(|m|)$, showing that $\phi_i$ is not a polytime reduction from $L_1$ to $L_2$.

Answer 2

If your result is a k digit integer, then finding the result is at most k times harder than finding the digit that is hardest to find.

There are functions where some digits may be easy to find, and some harder. For example, it is a lot easier to find the k-th digit of pi in hexadecimal than to find all of the first k hexadecimal digits, but the same is not known for decimal.

All depends on the function.