2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "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$? $\endgroup$ – David Richerby May 10 at 8:53
  • $\begingroup$ 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? $\endgroup$ – dkaeae May 10 at 11:19
  • 1
    $\begingroup$ What is $|\cdot|$? Absolute value doesn't make sense, given that the numbers are in $\mathbb{N}$... $\endgroup$ – Peter Taylor May 10 at 12:48
  • $\begingroup$ @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). $\endgroup$ – dkaeae May 10 at 12:57
1
$\begingroup$

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

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

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.

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

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.