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

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.

• "Heuristically I am thinking that for any function it is impossible to compute a digit of the computation without generally computing the function" Let $f(n)=2n$ ($n$ in binary) -- it's easy to compute the first and last digits of $f(\text{anything})$. Can you compute the 100th digit of $\pi$? Can you compute all of $\pi$? – David Richerby May 10 '19 at 8:53
• Also, I've just noticed the question text does not specify what kind of reduction it is you are talking about. Is it a Turing reduction? Many-one? Something else? – dkaeae May 10 '19 at 11:19
• What is $|\cdot|$? Absolute value doesn't make sense, given that the numbers are in $\mathbb{N}$... – Peter Taylor May 10 '19 at 12:48
• @PeterTaylor I believe $|n|$ means simply the length of the encoding of $n$. It is not explicit in the question text, but one should assume $n, k \in \{0,1\}^\ast$ here (which entails a bit of notation abuse, but it is a common enough convention). – dkaeae May 10 '19 at 12:57

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

• What does the second argument of $\phi_i$ indicate? The size of the alphabet? – Discrete lizard Jun 9 '19 at 15:02
• The function $\phi_i$ accepts a pair as input. In other words, $\phi_i(n,k)$ is the same as $\phi_i((n,k))$. – Yuval Filmus Jun 9 '19 at 15:19
• Ah, it's because $L_2$ is a language of pairs, of course. That is clear, thanks. – Discrete lizard Jun 9 '19 at 15:24

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.

• k times harder is still polynomial, doesn't that mean it is true for any function that fulfills the conditions? – Oren May 10 '19 at 9:42
• Find the one trillionth digit of pi. A factor of one trillion is huge. – gnasher729 May 10 '19 at 17:20