2
$\begingroup$

In "Computational complexity- A modern approach" book (page 117) for the lemma 7.12 (following) the author mentioned that if the ρ is efficiently computable ρ-coin cannot give probabilistic algorithm a new power. Then he states: "The exercises show that if ρ is not efficiently computable, then a ρ-coin can indeed provide additional power."

Lemma 7.12: A coin with Pr[Heads] = ρ can be simulated by a PTM in expected time O(1) provided the ith bit of ρ is computable in poly(i) time.

The exercise that supposed to show, if ρ is not efficiently computable, then a ρ-coin can indeed provide additional power is the following:

Exercise: Describe a real number ρ such that given a random coin that comes up “Heads” with probability ρ, a Turing machine can decide an undecidable language in polynomial time.

Now, how can we show that if ρ is not efficiently computable, then a ρ-coin can indeed provide an additional power for a probabilistic algorithm to decide some undeniable language in polynomial time?

*I removed the hint because it made me more confused but you can find it at the end of the book.

I strongly believe that this is a research level problem and proper to be discussed in theoretical computer science society because this is a high level question about computational complexity and this question has not been discussed anywhere else.

$\endgroup$

closed as off-topic by Jan Johannsen, Gamow, Emil Jeřábek, Sasho Nikolov, domotorp May 6 at 20:31

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Jan Johannsen, Gamow, Emil Jeřábek, Sasho Nikolov, domotorp
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Somehow I think I should use Chernoff bound but I don't know how. $\endgroup$ – Hope May 6 at 1:56
  • 5
    $\begingroup$ We don’t do homework problems here. Look up Chaitin’s constant. $\endgroup$ – Aryeh May 6 at 4:28
  • $\begingroup$ Aryeh, I checked Chaitin’s constant it seems it is not efficiently computable but how can it provide an additional power for probabilistic algorithm? $\endgroup$ – Hope May 6 at 13:50
  • $\begingroup$ OK, there's a minor trick -- see my answer below. $\endgroup$ – Aryeh May 6 at 15:01
4
$\begingroup$

I'll take as given the existence of Chaitin's constant $\Omega\in[0,1]$, and that knowing its first $k$ bits is equivalent to be able to decide the halting problem for all Turning machines of size up to $k$: https://en.wikipedia.org/wiki/Chaitin%27s_constant

Given access to an $\Omega$-biased coin, one can use Chernoff bounds to compute $\hat\Omega_k$, which agrees with $\Omega$ up to $k$ bits (i.e., $|\Omega-\hat\Omega_k|<1/2^{k+1}$), by sampling the coin $O(2^{2k})$ times. Now this is exponential in $k$ and is actually tight, so how does this square with the problem statement: "Describe a real number $\rho$ such that given a random coin that comes up “Heads” with probability $\rho$, a Turing machine can decide an undecidable language in polynomial time" ?

The trick is to use a very inefficient encoding for the undecidable language. Fix a universal encoding (the same one used to define $\Omega$) and consider the language $L$, which consists of all Turing machine descriptions $<M>$, such that $M$ halts on all inputs. Clearly, $L$ is undecidable. Now order $L$ in lexicographic order where $<M_i>$ is the $i$th word, and define $L'$ to consist of the words $<M_i'>$, where $M_i'$ is a TM equivalent to $M_i$ (the two halt on and accept the same set of inputs), but $M_i'$ contains an additional $2^i$ dummy states.

Thus, to determine whether a word $x$ belongs to the undecidable language $L'$, one only needs to know $O(\log|x|)$ bits of $\Omega$, which is feasible in expected poly$(|x|)$ time via the argument above.

$\endgroup$
  • $\begingroup$ Thanks, Aryeh! I still have a little problem understanding it but your logic seems right. I just want to add Chaitin's constant is a real number that is not computable. $\endgroup$ – Hope May 7 at 4:17
  • $\begingroup$ One more question, the book didn't mention Chaitin's constant at all and I didn't heard of that before. It seems without knowing of Chaitin's constant it is impossible to do the prove. Where should I learn this? Can you please introduce a good reference that can be more helpful? $\endgroup$ – Hope May 7 at 4:42
  • $\begingroup$ That's a good pedagogical question. Maybe the author expects you to discover something like $\Omega$ on your own. For background on the latter, you can look here amazon.com/… $\endgroup$ – Aryeh May 7 at 7:13
  • $\begingroup$ You just need to come up with the idea to encode the HALTING language as an infinite string. I don't think that's unreasonable. $\endgroup$ – Sasho Nikolov May 8 at 7:49
  • $\begingroup$ Indeed— though one does need to make the encoding of the language “exponentially inefficient”, I think. $\endgroup$ – Aryeh May 8 at 7:59

Not the answer you're looking for? Browse other questions tagged or ask your own question.