Skip to main content
Computer Science

Return to Answer

Mod Moved Comments To Chat
Post Undeleted by D.W.♦
Correct the answer
Source Link
D.W. ♦
D.W. ♦
  • 165.6k
  • 21
  • 230
  • 490

The sketch of the approach is as follows:

  1. Amplify the correctness of the algorithm, so it is correct with probability exponentially close to 1 on any particular input.
  2. Use a PRNG instead of true-random bits, and show that its correctness remains exponentially close to 1.
  3. Show that, if you choose a random seed to the PRNG, there is a non-zero probability that the resulting algorithm is correct on all inputs.
  4. Conclude via the probabilistic method that there exists a deterministic algorithm that is correct on all inputs.

In more detail:

Let $A$ be a BPP algorithm for the problem, i.e., $A$ runs in polynomial time, uses randomness, and is correct with probability at least 2/3 on every input.

By standard results on BPP, we can amplify the correctness probability as much as desired by running $A$ multiple times and taking a majority vote. In particular, we can achieve correctness probability $\ge 1 - 2^{-6n}$ on all inputs of length $n$, with only polynomially many repetitions. (Proof is by a Chernoff-Hoeffding bound and is covered in many lecture notes under names like error reduction.) We obtain a new algorithm $A'$, that also runs in polynomial time.

The probability of incorrect output, for a specific fixed input, is $\le 2^{-6n}$. What is the probability that there exists any input at all on which it produces an incorrect output? By a union bound, this is

$$\le \sum_{n=1}^{\infty} \sum_{x \in \{0,1\}^n} 2^{-6n} = \sum_{n=1}^{\infty} 2^n \times 2^{-6n} = \sum_{n=1}^{\infty} 2^{-5n} = \frac{1}{31}.$$

[ignore everything below, I am still writing out the rest of the answer]

Now let's assume we have a PRNG that requires exponential time to distinguish its output from random. In other words, if the seed length is $s$, it takes at least $2^s$ steps to distinguish its output from random. (This is a strong assumption, stronger than standard cryptographic assumptions: e.g., it needs to resist super-polynomial sub-exponential time distinguishers.) (Recall that the definition of what it means for a PRNG to be cryptographically strong is that there does not exist any efficient distinguisher, i.e., any efficient algorithm that can distinguish its output from random bits. See https://crypto.stackexchange.com/q/12436/351, https://crypto.stackexchange.com/q/39186/351, https://crypto.stackexchange.com/q/32267/351, https://crypto.stackexchange.com/q/51882/351, https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator#Definitions, https://en.wikipedia.org/wiki/Computational_indistinguishability.)

Suppose the running time of $A'$$A$ is $O(n^5)$. Let's instantiate the PRNG with seed length $s=10 \lg n$. Let $\hat{A}$ denote running $A'$$A$, but using the output of the PRNG (on a seed generated uniformly at random) instead of truly random bits, and $\hat{A}_k$ denote running $\hat{A}$ with the seed fixed to $k$.

By our assumption on the security of the PRNG, distinguishing the PRNG's output from random needs at least $2^s=n^{10}$ steps. Since the running time of $A'$$A$ is much less than that, $A'$$A$ cannot distinguish the PRNG's output from random. Consequently, the output of $A'$$A$ when run on the PRNG's output is very similar to its output when run on truly random bits. In other wordsparticular, the output of $\hat{A}$ is very similar to the output ofcorrect with probability at least $A'$$7/12$ (say) on every input.

In particular (Why? If not, if we runyou could use $\hat{A}$ (if we choose a random $s$-bit seed forto distinguish the PRNG and then running $A'$ with bitsPRNG's output from the PRNG instead of true random bits.), we obtain a randomized algorithm whose running time is $O(n^5)$ and such

This means that, for every input $x$, it hasout of all $2^s$ possible seeds for the PRNG, at least $1-2^{-6n}-\varepsilon$ probability$(7/12) \cdot 2^s$ of producing the correct output on input $x$, wherethem cause $\varepsilon$ is very small. Let's suppose$\hat{A}$ to give the PRNG is good enough that $\varepsilon \le 2^{-6n}$correct answer.

Now suppose we pick In particular, a random $s$-bit seed $k$ and ask whetherstrict majority of the seeds cause $\hat{A}_k$ produces$\hat{A}$ to output the correct output on all inputsanswer $x$. Well,(and this is true for any particular $n$-bitall input $x$, the probability that it produces an incorrect input is $\le 2^{-3n}$). Therefore, by a union bound, the probability that there exists any input on which it produces an incorrect output is

$$\le \sum_{n=1}^{\infty} \sum_{x \inTherefore, we'll construct a new algorithm {0$B$,1}^n} 2^{-2n} = \sum_{n=1}^{\infty} 2^n \times 2^{-2n} = \sum_{n=1}^{\infty} 2^{-n} = 1

Now which works as follows: enumerate all $2^s=n^{10}$$2^s=2^{10\lg n}=n^{10}$ possible seeds for the PRNG, and compute the output of $A$-with-pseudorandom-bits-from-this-PRNG for each run $\hat{A}(x)$ on that seed, and take a majority vote of those seedsthe answers. By the above remarks, we knows that a 50.1% fraction of the outputs will be correct. So taking a majority vote of those outputs will yieldis guaranteed to be the correct answer (always, for all $x$).

This givesWe find that $B$ is a deterministic algorithm that always produces the correct answer. Also, and hasthe running time of $B$ is $O(n^{15})$, i.e.since we run $A$ $n^{10}$ times, and each time takes $O(n^5)$ time. It follows that $B$ runs in polynomial running time, so $B$ is a P algorithm.

This is just a sketch of the idea. There are details that need to be filled in. For instance, it's not trueWe have proven that anif there is any BPP algorithm either can or can't distinguish PRNG from random. It's not black-and-white. Ratherfor some problem, itthen there is a matter of shades of grey, which we measure with the advantage of a distinguishingP algorithm. We need to formalize the assumptions about the advantage of all distinguishers as a function of their running time for that problem, and applyassuming there are PRNGs that require exponential time to the above proof. But I think this gives you the main ideasbreak.

The sketch of the approach is as follows:

  1. Amplify the correctness of the algorithm, so it is correct with probability exponentially close to 1 on any particular input.
  2. Use a PRNG instead of true-random bits, and show that its correctness remains exponentially close to 1.
  3. Show that, if you choose a random seed to the PRNG, there is a non-zero probability that the resulting algorithm is correct on all inputs.
  4. Conclude via the probabilistic method that there exists a deterministic algorithm that is correct on all inputs.

In more detail:

Let $A$ be a BPP algorithm for the problem, i.e., $A$ runs in polynomial time, uses randomness, and is correct with probability at least 2/3 on every input.

By standard results on BPP, we can amplify the correctness probability as much as desired by running $A$ multiple times and taking a majority vote. In particular, we can achieve correctness probability $\ge 1 - 2^{-6n}$ on all inputs of length $n$, with only polynomially many repetitions. (Proof is by a Chernoff-Hoeffding bound and is covered in many lecture notes under names like error reduction.) We obtain a new algorithm $A'$, that also runs in polynomial time.

The probability of incorrect output, for a specific fixed input, is $\le 2^{-6n}$. What is the probability that there exists any input at all on which it produces an incorrect output? By a union bound, this is

$$\le \sum_{n=1}^{\infty} \sum_{x \in \{0,1\}^n} 2^{-6n} = \sum_{n=1}^{\infty} 2^n \times 2^{-6n} = \sum_{n=1}^{\infty} 2^{-5n} = \frac{1}{31}.$$

[ignore everything below, I am still writing out the rest of the answer]

Now let's assume we have a PRNG that requires exponential time to distinguish its output from random. In other words, if the seed length is $s$, it takes at least $2^s$ steps to distinguish its output from random. (This is a strong assumption, stronger than standard cryptographic assumptions: e.g., it needs to resist super-polynomial sub-exponential time distinguishers.)

Suppose the running time of $A'$ is $O(n^5)$. Let's instantiate the PRNG with seed length $s=10 \lg n$. Let $\hat{A}$ denote running $A'$, but using the output of the PRNG (on a seed generated uniformly at random) instead of truly random bits, and $\hat{A}_k$ denote running $\hat{A}$ with the seed fixed to $k$.

By our assumption on the security of the PRNG, distinguishing the PRNG's output from random needs at least $2^s=n^{10}$ steps. Since the running time of $A'$ is much less than that, $A'$ cannot distinguish the PRNG's output from random. Consequently, the output of $A'$ when run on the PRNG's output is very similar to its output when run on truly random bits. In other words, the output of $\hat{A}$ is very similar to the output of $A'$.

In particular, if we run $\hat{A}$ (if we choose a random $s$-bit seed for the PRNG and then running $A'$ with bits from the PRNG instead of true random bits), we obtain a randomized algorithm whose running time is $O(n^5)$ and such that for every input $x$, it has at least $1-2^{-6n}-\varepsilon$ probability of producing the correct output on input $x$, where $\varepsilon$ is very small. Let's suppose the PRNG is good enough that $\varepsilon \le 2^{-6n}$.

Now suppose we pick a random $s$-bit seed $k$ and ask whether $\hat{A}_k$ produces the correct output on all inputs $x$. Well, for any particular $n$-bit input $x$, the probability that it produces an incorrect input is $\le 2^{-3n}$. Therefore, by a union bound, the probability that there exists any input on which it produces an incorrect output is

$$\le \sum_{n=1}^{\infty} \sum_{x \in {0,1}^n} 2^{-2n} = \sum_{n=1}^{\infty} 2^n \times 2^{-2n} = \sum_{n=1}^{\infty} 2^{-n} = 1

Now enumerate all $2^s=n^{10}$ possible seeds for the PRNG, and compute the output of $A$-with-pseudorandom-bits-from-this-PRNG for each of those seeds. By the above, we knows that a 50.1% fraction of the outputs will be correct. So taking a majority vote of those outputs will yield the correct answer.

This gives a deterministic algorithm that always produces the correct answer, and has running time $O(n^{15})$, i.e., polynomial running time.

This is just a sketch of the idea. There are details that need to be filled in. For instance, it's not true that an algorithm either can or can't distinguish PRNG from random. It's not black-and-white. Rather, it is a matter of shades of grey, which we measure with the advantage of a distinguishing algorithm. We need to formalize the assumptions about the advantage of all distinguishers as a function of their running time, and apply that to the above proof. But I think this gives you the main ideas.

Let $A$ be a BPP algorithm for the problem, i.e., $A$ runs in polynomial time, uses randomness, and is correct with probability at least 2/3 on every input.

Now let's assume we have a PRNG that requires exponential time to distinguish its output from random. In other words, if the seed length is $s$, it takes at least $2^s$ steps to distinguish its output from random. (This is a strong assumption, stronger than standard cryptographic assumptions: e.g., it needs to resist super-polynomial sub-exponential time distinguishers.) (Recall that the definition of what it means for a PRNG to be cryptographically strong is that there does not exist any efficient distinguisher, i.e., any efficient algorithm that can distinguish its output from random bits. See https://crypto.stackexchange.com/q/12436/351, https://crypto.stackexchange.com/q/39186/351, https://crypto.stackexchange.com/q/32267/351, https://crypto.stackexchange.com/q/51882/351, https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator#Definitions, https://en.wikipedia.org/wiki/Computational_indistinguishability.)

Suppose the running time of $A$ is $O(n^5)$. Let's instantiate the PRNG with seed length $s=10 \lg n$. Let $\hat{A}$ denote running $A$, but using the output of the PRNG (on a seed generated uniformly at random) instead of truly random bits.

By our assumption on the security of the PRNG, distinguishing the PRNG's output from random needs at least $2^s=n^{10}$ steps. Since the running time of $A$ is much less than that, $A$ cannot distinguish the PRNG's output from random. Consequently, the output of $A$ when run on the PRNG's output is very similar to its output when run on truly random bits. In particular, $\hat{A}$ is correct with probability at least $7/12$ (say) on every input. (Why? If not, you could use $\hat{A}$ to distinguish the PRNG's output from random.)

This means that, for every input $x$, out of all $2^s$ possible seeds for the PRNG, at least $(7/12) \cdot 2^s$ of them cause $\hat{A}$ to give the correct answer. In particular, a strict majority of the seeds cause $\hat{A}$ to output the correct answer (and this is true for all input $x$).

Therefore, we'll construct a new algorithm $B$, which works as follows: enumerate all $2^s=2^{10\lg n}=n^{10}$ possible seeds, for each run $\hat{A}(x)$ on that seed, and take a majority vote of the answers. By the above remarks, the majority is guaranteed to be the correct answer (always, for all $x$).

We find that $B$ is a deterministic algorithm that always produces the correct answer. Also, the running time of $B$ is $O(n^{15})$, since we run $A$ $n^{10}$ times, and each time takes $O(n^5)$ time. It follows that $B$ runs in polynomial time, so $B$ is a P algorithm.

We have proven that if there is any BPP algorithm for some problem, then there is a P algorithm for that problem, assuming there are PRNGs that require exponential time to break.

Post Deleted by D.W.♦
added 2993 characters in body
Source Link
D.W. ♦
D.W. ♦
  • 165.6k
  • 21
  • 230
  • 490

I thinkThe sketch of the intuitionapproach is as follows:

  1. Amplify the correctness of the algorithm, so it is correct with probability exponentially close to 1 on any particular input.
  2. Use a PRNG instead of true-random bits, and show that its correctness remains exponentially close to 1.
  3. Show that, if you choose a random seed to the PRNG, there is a non-zero probability that the resulting algorithm is correct on all inputs.
  4. Conclude via the probabilistic method that there exists a deterministic algorithm that is correct on all inputs.

In more detail:

Let $A$ be a BPP algorithm for the problem, i. Suppose youe., $A$ runs in polynomial time, uses randomness, and is correct with probability at least 2/3 on every input.

By standard results on BPP, we can amplify the correctness probability as much as desired by running $A$ multiple times and taking a majority vote. In particular, we can achieve correctness probability $\ge 1 - 2^{-6n}$ on all inputs of length $n$, with only polynomially many repetitions. (Proof is by a Chernoff-Hoeffding bound and is covered in many lecture notes under names like error reduction.) We obtain a new algorithm $A'$, that also runs in polynomial time.

The probability of incorrect output, for a specific fixed input, is $\le 2^{-6n}$. What is the probability that there exists any input at all on which it produces an incorrect output? By a union bound, this is

$$\le \sum_{n=1}^{\infty} \sum_{x \in \{0,1\}^n} 2^{-6n} = \sum_{n=1}^{\infty} 2^n \times 2^{-6n} = \sum_{n=1}^{\infty} 2^{-5n} = \frac{1}{31}.$$

[ignore everything below, I am still writing out the rest of the answer]

Now let's assume we have a PRNG that takesrequires exponential time to distinguish its output from random, i.e. In other words, if the seed length is $s$, it takes at least $2^s$ steps to distinguish its output from random. (This is a strong assumption, stronger than standard cryptographic assumptions: e.g., it needs to resist super-polynomial sub-exponential time distinguishers.)

Consider any BPP algorithm $A$ whoseSuppose the running time of $A'$ is $O(n^5)$. Suppose we Let's instantiate the PRNG with seed length $s=10 \lg n$, and run algorithm. Let $A$$\hat{A}$ denote running $A'$, but using the output of the PRNG (on a seed generated uniformly at random) instead of usingtruly random bits, we useand $\hat{A}_k$ denote running $\hat{A}$ with the outputseed fixed to $k$.

By our assumption on the security of the PRNG. Distinguishing, distinguishing the PRNG's output from random needs at least $2^s=n^{10}$ steps, and since $A$'s. Since the running time of $A'$ is much less than that, $A$$A'$ cannot distinguish the PRNGPRNG's output from random. Consequently, the behavioroutput of $A$$A'$ when run on the PRNG's output is very similar to its output when run on truly random bits. In other words, the output of $\hat{A}$ is very similar to the behavioroutput of $A$ when using pseudorandom$A'$.

In particular, if we run $\hat{A}$ (if we choose a random $s$-bit seed for the PRNG and then running $A'$ with bits generated byfrom the PRNG. It follows instead of true random bits), we obtain a randomized algorithm whose running time is $O(n^5)$ and such that for every input $A$ is correct, say$x$, it has at least 50.1%$1-2^{-6n}-\varepsilon$ probability of producing the timecorrect output on input $x$, where $\varepsilon$ is very small. Let's suppose the PRNG is good enough that $\varepsilon \le 2^{-6n}$.

Now suppose we pick a random $s$-bit seed $k$ and ask whether $\hat{A}_k$ produces the correct output on all inputs $x$. Well, for any particular $n$-bit input $x$, the probability that it produces an incorrect input is $\le 2^{-3n}$. Therefore, by a union bound, the probability that there exists any input on which it produces an incorrect output is

$$\le \sum_{n=1}^{\infty} \sum_{x \in {0,1}^n} 2^{-2n} = \sum_{n=1}^{\infty} 2^n \times 2^{-2n} = \sum_{n=1}^{\infty} 2^{-n} = 1

I think the intuition is as follows. Suppose you have a PRNG that takes exponential time to distinguish from random, i.e., if the seed length is $s$, it takes at least $2^s$ steps to distinguish from random.

Consider any BPP algorithm $A$ whose running time is $O(n^5)$. Suppose we instantiate the PRNG with seed length $s=10 \lg n$, and run algorithm $A$, but instead of using random bits, we use the output of the PRNG. Distinguishing the PRNG's output from random needs at least $2^s=n^{10}$ steps, and since $A$'s running time is much less than that, $A$ cannot distinguish the PRNG from random. Consequently, the behavior of $A$ on random bits is very similar to the behavior of $A$ when using pseudorandom bits generated by the PRNG. It follows that $A$ is correct, say, at least 50.1% of the time.

The sketch of the approach is as follows:

  1. Amplify the correctness of the algorithm, so it is correct with probability exponentially close to 1 on any particular input.
  2. Use a PRNG instead of true-random bits, and show that its correctness remains exponentially close to 1.
  3. Show that, if you choose a random seed to the PRNG, there is a non-zero probability that the resulting algorithm is correct on all inputs.
  4. Conclude via the probabilistic method that there exists a deterministic algorithm that is correct on all inputs.

In more detail:

Let $A$ be a BPP algorithm for the problem, i.e., $A$ runs in polynomial time, uses randomness, and is correct with probability at least 2/3 on every input.

By standard results on BPP, we can amplify the correctness probability as much as desired by running $A$ multiple times and taking a majority vote. In particular, we can achieve correctness probability $\ge 1 - 2^{-6n}$ on all inputs of length $n$, with only polynomially many repetitions. (Proof is by a Chernoff-Hoeffding bound and is covered in many lecture notes under names like error reduction.) We obtain a new algorithm $A'$, that also runs in polynomial time.

The probability of incorrect output, for a specific fixed input, is $\le 2^{-6n}$. What is the probability that there exists any input at all on which it produces an incorrect output? By a union bound, this is

$$\le \sum_{n=1}^{\infty} \sum_{x \in \{0,1\}^n} 2^{-6n} = \sum_{n=1}^{\infty} 2^n \times 2^{-6n} = \sum_{n=1}^{\infty} 2^{-5n} = \frac{1}{31}.$$

[ignore everything below, I am still writing out the rest of the answer]

Now let's assume we have a PRNG that requires exponential time to distinguish its output from random. In other words, if the seed length is $s$, it takes at least $2^s$ steps to distinguish its output from random. (This is a strong assumption, stronger than standard cryptographic assumptions: e.g., it needs to resist super-polynomial sub-exponential time distinguishers.)

Suppose the running time of $A'$ is $O(n^5)$. Let's instantiate the PRNG with seed length $s=10 \lg n$. Let $\hat{A}$ denote running $A'$, but using the output of the PRNG (on a seed generated uniformly at random) instead of truly random bits, and $\hat{A}_k$ denote running $\hat{A}$ with the seed fixed to $k$.

By our assumption on the security of the PRNG, distinguishing the PRNG's output from random needs at least $2^s=n^{10}$ steps. Since the running time of $A'$ is much less than that, $A'$ cannot distinguish the PRNG's output from random. Consequently, the output of $A'$ when run on the PRNG's output is very similar to its output when run on truly random bits. In other words, the output of $\hat{A}$ is very similar to the output of $A'$.

In particular, if we run $\hat{A}$ (if we choose a random $s$-bit seed for the PRNG and then running $A'$ with bits from the PRNG instead of true random bits), we obtain a randomized algorithm whose running time is $O(n^5)$ and such that for every input $x$, it has at least $1-2^{-6n}-\varepsilon$ probability of producing the correct output on input $x$, where $\varepsilon$ is very small. Let's suppose the PRNG is good enough that $\varepsilon \le 2^{-6n}$.

Now suppose we pick a random $s$-bit seed $k$ and ask whether $\hat{A}_k$ produces the correct output on all inputs $x$. Well, for any particular $n$-bit input $x$, the probability that it produces an incorrect input is $\le 2^{-3n}$. Therefore, by a union bound, the probability that there exists any input on which it produces an incorrect output is

$$\le \sum_{n=1}^{\infty} \sum_{x \in {0,1}^n} 2^{-2n} = \sum_{n=1}^{\infty} 2^n \times 2^{-2n} = \sum_{n=1}^{\infty} 2^{-n} = 1

Source Link
D.W. ♦
D.W. ♦
  • 165.6k
  • 21
  • 230
  • 490

I think the intuition is as follows. Suppose you have a PRNG that takes exponential time to distinguish from random, i.e., if the seed length is $s$, it takes at least $2^s$ steps to distinguish from random.

Consider any BPP algorithm $A$ whose running time is $O(n^5)$. Suppose we instantiate the PRNG with seed length $s=10 \lg n$, and run algorithm $A$, but instead of using random bits, we use the output of the PRNG. Distinguishing the PRNG's output from random needs at least $2^s=n^{10}$ steps, and since $A$'s running time is much less than that, $A$ cannot distinguish the PRNG from random. Consequently, the behavior of $A$ on random bits is very similar to the behavior of $A$ when using pseudorandom bits generated by the PRNG. It follows that $A$ is correct, say, at least 50.1% of the time.

Now enumerate all $2^s=n^{10}$ possible seeds for the PRNG, and compute the output of $A$-with-pseudorandom-bits-from-this-PRNG for each of those seeds. By the above, we knows that a 50.1% fraction of the outputs will be correct. So taking a majority vote of those outputs will yield the correct answer.

This gives a deterministic algorithm that always produces the correct answer, and has running time $O(n^{15})$, i.e., polynomial running time.

This is just a sketch of the idea. There are details that need to be filled in. For instance, it's not true that an algorithm either can or can't distinguish PRNG from random. It's not black-and-white. Rather, it is a matter of shades of grey, which we measure with the advantage of a distinguishing algorithm. We need to formalize the assumptions about the advantage of all distinguishers as a function of their running time, and apply that to the above proof. But I think this gives you the main ideas.