<p>There is a particular use of randomness that is fairly common in parameterized complexity, which involves either the <a href="http://en.wikipedia.org/wiki/Isolation_lemma">isolation lemma</a>, or the <a href="http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma">Schwartz-Zippel lemma</a>. Roughly, it involves defining a large enumeration of potential solutions, and arguing that all non-solutions "pair up" (e.g., are counted twice) while the desired solution(s) are counted only once. Then one either uses the isolation lemma to produce a situation with only one smallest solution, or defines a large corresponding formal polynomial over GF$(2^\ell)$ and uses Schwartz-Zippel to test whether any non-paired term exists. (I'm sure there's a good overview or survey out there, but at the moment it slips my mind.) </p>

<p>That said, I can only think of two cases where this usage would lead to a difference between BPP and P.</p>

<p>The first is the recent algorithm for <a href="http://link.springer.com/chapter/10.1007/978-3-662-43948-7_18">Shortest two disjoint paths</a> (<a href="http://thorehusfeldt.files.wordpress.com/2010/08/spdp-e5d5661.pdf">author's PDF</a>), Björklund and Husfeldt, ICALP 2014. </p>

<p>The second is a parameterized problem -- find a simple cycle through a set K of specified elements in a graph, i.e., something like a Steiner cycle problem. When $|K|=O(\log n)$, this problem is in BPP by Björklund, Husfeldt, Taslaman, SODA 2012 (<a href="http://siam.omnibooksonline.com/2012SODA/data/papers/247.pdf">link</a>). (There is a previous deterministic algorithm, but its dependency on $|K|$ is exponentially worse.) Thus, one could define the problem "log-Steiner Cycle" (or whatever you want to call it), and it would fit your question.</p>

CC BY-SA 3.0
2014-12-28T13:37:49.930Z
2014-12-28T13:37:49.930Z
Magnus Wahlström
<p>If you're asking for independent problems, how about:</p>

<blockquote>
  <p>Find a prime in the interval $[N, 5N/4]$,<br>
  Find two primes whose product is in the interval $[N, 9N/8]$,<br>
  Find three primes whose product is in the interval $[N, 17N/16]$,<br>
  Find four primes whose product is in the interval $[N, 33N/32]$,<br>
  Find five primes whose product is in the interval $[N, 65N/64]$,<br>
  $\ldots$. </p>
</blockquote>

<p>It's overwhelmingly likely that if you actually had a polynomial algorithm to solve the first of these, you would have a polynomial algorithm for all of them. But I don't see how to formally reduce any of these to any of the others. Of course, the problem</p>

<blockquote>
  <p>Find a prime in the interval $[N, N+\log^{17} N ]$</p>
</blockquote>

<p>solves all of these.</p>

CC BY-SA 3.0
2014-12-31T04:42:33.053Z
To be precise, what is the decision version of these problems you have in mind? Thanks.
usul
CC BY-SA 3.0
2015-01-01T14:17:10.433Z
@usul: I don't have a decision version of these problems in mind. Do I need to? I realize that technically, BPP only consists of decision problems. Most of the time, decision problems and function problems are more or less equivalent, which means that you can consider just  decision problems without loss of generality. I'm not sure that's true for this question, and I don't know whether the OP only cares about decision problems or not.
Peter Shor 
CC BY-SA 3.0
2015-01-01T20:57:51.490Z
I'm just asking because I don't know exactly when important subtleties arise. I think there should be some function problems that are known unconditionally to be in "BPP" and not "P", e.g. produce a string of Kolmogorov complexity $n$ (?). So I thought the question would point toward decision problems, and was wondering if a valid decision version of your answer (given current knowledge) would be e.g. "is there a prime in $[N,5N/4]$?"
usul
CC BY-SA 3.0
2015-01-22T22:22:58.510Z
@usul: For the question: "is there a prime in $[N, 5N/4]$?", it is known that a constant-time algorithm exists. It looks like: Say *"yes"* when $N > 10^6$ and check explicitly when $N \leq 10^6$. You need some [number theory](http://en.wikipedia.org/wiki/Bertrand%27s_postulate) to prove it works.
Peter Shor 
CC BY-SA 3.0
2015-01-23T07:28:30.700Z
Ok, sure/fine. I think I agree with Kaveh's comment in [this question](http://cstheory.stackexchange.com/questions/4882/finding-a-prime-greater-than-a-given-bound) that a natural corresponding decision problem is, given $a,b$, is there a prime in $[a,b]$?
usul
CC BY-SA 3.0
2014-12-28T13:35:47.233Z
2014-12-28T13:35:47.233Z
Peter Shor 
<p>I'm not an expert, but perhaps some (not-so-natural?) examples can be directly derived using the technique of deterministically reducing <em>BPP search problems</em> to <em>BPP decision problems</em>, presented in:</p>

<p><a href="http://link.springer.com/chapter/10.1007%2F978-3-642-22670-0_20">Oded Goldreich, In a World of P=BPP. Studies in Complexity and Cryptography 2011: 191-232</a></p>

<p>In particular see <strong>Theorem 3.5:</strong> (reducing search to decision): For every BPP-search problem $(R_{yes},R_{no})$, there exists a binary relation $R$ such that $R_{yes} \subseteq R \subseteq (\{0, 1\}^∗ \times \{0, 1\}^∗) \setminus R_{no}$ and solving the search problem
of $R$ is deterministically reducible to some decisional problem in BPP, denoted $\Pi$. Furthermore, the time-complexity of the reduction is linear in the probabilistic time-complexity of finding solutions for $(R_{yes},R_{no})$, whereas the probabilistic time-complexity of $\Pi$ is the product of a quadratic polynomial
and the probabilistic time-complexity of the decision procedure guaranteed for $(R_{yes},R_{no})$.</p>

<p>The theorem can be extended to general construction problems, for example (see <strong>Corollary 3.9</strong>) consider the problem of finding a prime in a large enough interval :</p>

<p>For any fixed $c &gt; 7/12$, on input $N$, find a prime in the interval $[N, N +  N^c]$</p>

<p>The randomized algorithm runs in expected polynomial time; no deterministic polynomial time algorithm is known; but if BPP=P such deterministic polynomial time algorithm must exist (because it can be reduced to a BPP-decision problem).</p>

CC BY-SA 3.0
2014-12-28T01:34:22.347Z
2014-12-28T01:34:22.347Z
Marzio De Biasi
<p><strong>What problems are known to belong to $\mathsf{BPP}$ but not known to belong to $\mathsf P$?</strong></p>

<p>More precisely, I am interested in <em>independent</em> problems, that is whose derandomizations are not known to be equivalent. For instance, it is known that derandomizing PIT and multivariate polynomial factorization are <a href="http://eccc.hpi-web.de/report/2014/001/download/">equivalent</a> and I would count them as only one problem. </p>

<p>The motivation of my question is that it is common to say that <em>"there are few problems in $\mathsf{BPP}$ not known to be in $\mathsf{P}$"</em>, but I was not able to find a list of them. In particular, if I have to cite problems in this category, I usually cite the factorization of univariate polynomials over finite fields, or the factorization of multivariate polynomials. I suppose that there exist examples that are not related to polynomial factorization, for instance in other domains such as graph theory or formal language theory.</p>

<p>P.S.: I find curious that a similar question does not exist on this website yet. My apologies if I simply did not find it (or them)! </p>

CC BY-SA 3.0
2014-12-27T15:36:01.340Z
The answers to this post contain two examples http://cstheory.stackexchange.com/questions/11425/problem-in-bpp-but-not-known-to-be-in-rp-or-co-rp
Mohammad Al-Turkistany
<derandomization>
Problems in $\mathsf{BPP}$ not known to be in $\mathsf P$?
Bruno
# Problems in $\mathsf{BPP}$ not known to be in $\mathsf P$?

(Asked by: username_0 on 2014-12-27)

**What problems are known to belong to $\mathsf{BPP}$ but not known to belong to $\mathsf P$?**

More precisely, I am interested in *independent* problems, that is whose derandomizations are not known to be equivalent. For instance, it is known that derandomizing PIT and multivariate polynomial factorization are [equivalent](http://eccc.hpi-web.de/report/2014/001/download/) and I would count them as only one problem.

The motivation of my question is that it is common to say that *"there are few problems in $\mathsf{BPP}$ not known to be in $\mathsf{P}$"*, but I was not able to find a list of them. In particular, if I have to cite problems in this category, I usually cite the factorization of univariate polynomials over finite fields, or the factorization of multivariate polynomials. I suppose that there exist examples that are not related to polynomial factorization, for instance in other domains such as graph theory or formal language theory.

P.S.: I find curious that a similar question does not exist on this website yet. My apologies if I simply did not find it (or them)!

**Tags:** derandomization

> **Comments:**
> **username_1**: The answers to this post contain two examples http://cstheory.stackexchange.com/questions/11425/problem-in-bpp-but-not-known-to-be-in-rp-or-co-rp  

---

## 3 answers

### Answer by username_3 on 2014-12-28. Score: 15

If you're asking for independent problems, how about:

> Find a prime in the interval $[N, 5N/4]$,  
> Find two primes whose product is in the interval $[N, 9N/8]$,  
> Find three primes whose product is in the interval $[N, 17N/16]$,  
> Find four primes whose product is in the interval $[N, 33N/32]$,  
> Find five primes whose product is in the interval $[N, 65N/64]$,  
> $\ldots$.

It's overwhelmingly likely that if you actually had a polynomial algorithm to solve the first of these, you would have a polynomial algorithm for all of them. But I don't see how to formally reduce any of these to any of the others. Of course, the problem

> Find a prime in the interval $[N, N+\log^{17} N ]$

solves all of these.

> **Comments:**
> **username_4**: To be precise, what is the decision version of these problems you have in mind? Thanks.  
> **username_3**: @username_4: I don't have a decision version of these problems in mind. Do I need to? I realize that technically, BPP only consists of decision problems. Most of the time, decision problems and function problems are more or less equivalent, which means that you can consider just  decision problems without loss of generality. I'm not sure that's true for this question, and I don't know whether the OP only cares about decision problems or not.  
> **username_4**: I'm just asking because I don't know exactly when important subtleties arise. I think there should be some function problems that are known unconditionally to be in "BPP" and not "P", e.g. produce a string of Kolmogorov complexity $n$ (?). So I thought the question would point toward decision problems, and was wondering if a valid decision version of your answer (given current knowledge) would be e.g. "is there a prime in $[N,5N/4]$?"  
> **username_3**: @username_4: For the question: "is there a prime in $[N, 5N/4]$?", it is known that a constant-time algorithm exists. It looks like: Say *"yes"* when $N > 10^6$ and check explicitly when $N \leq 10^6$. You need some [number theory](http://en.wikipedia.org/wiki/Bertrand%27s_postulate) to prove it works.  
> **username_4**: Ok, sure/fine. I think I agree with Kaveh's comment in [this question](http://cstheory.stackexchange.com/questions/4882/finding-a-prime-greater-than-a-given-bound) that a natural corresponding decision problem is, given $a,b$, is there a prime in $[a,b]$?  

---

### Answer by username_2 on 2014-12-28. Score: 11

There is a particular use of randomness that is fairly common in parameterized complexity, which involves either the [isolation lemma](http://en.wikipedia.org/wiki/Isolation_lemma), or the [Schwartz-Zippel lemma](http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma). Roughly, it involves defining a large enumeration of potential solutions, and arguing that all non-solutions "pair up" (e.g., are counted twice) while the desired solution(s) are counted only once. Then one either uses the isolation lemma to produce a situation with only one smallest solution, or defines a large corresponding formal polynomial over GF$(2^\ell)$ and uses Schwartz-Zippel to test whether any non-paired term exists. (I'm sure there's a good overview or survey out there, but at the moment it slips my mind.)

That said, I can only think of two cases where this usage would lead to a difference between BPP and P.

The first is the recent algorithm for [Shortest two disjoint paths](http://link.springer.com/chapter/10.1007/978-3-662-43948-7_18) ([author's PDF](http://thorehusfeldt.files.wordpress.com/2010/08/spdp-e5d5661.pdf)), Björklund and Husfeldt, ICALP 2014.

The second is a parameterized problem -- find a simple cycle through a set K of specified elements in a graph, i.e., something like a Steiner cycle problem. When $|K|=O(\log n)$, this problem is in BPP by Björklund, Husfeldt, Taslaman, SODA 2012 ([link](http://siam.omnibooksonline.com/2012SODA/data/papers/247.pdf)). (There is a previous deterministic algorithm, but its dependency on $|K|$ is exponentially worse.) Thus, one could define the problem "log-Steiner Cycle" (or whatever you want to call it), and it would fit your question.


---

### Answer by username_5 on 2014-12-28. Score: 9

I'm not an expert, but perhaps some (not-so-natural?) examples can be directly derived using the technique of deterministically reducing *BPP search problems* to *BPP decision problems*, presented in:

[Oded Goldreich, In a World of P=BPP. Studies in Complexity and Cryptography 2011: 191-232](http://link.springer.com/chapter/10.1007%2F978-3-642-22670-0_20)

In particular see **Theorem 3.5:** (reducing search to decision): For every BPP-search problem $(R\_{yes},R\_{no})$, there exists a binary relation $R$ such that $R\_{yes} \subseteq R \subseteq (\{0, 1\}^∗ \times \{0, 1\}^∗) \setminus R\_{no}$ and solving the search problem
of $R$ is deterministically reducible to some decisional problem in BPP, denoted $\Pi$. Furthermore, the time-complexity of the reduction is linear in the probabilistic time-complexity of finding solutions for $(R\_{yes},R\_{no})$, whereas the probabilistic time-complexity of $\Pi$ is the product of a quadratic polynomial
and the probabilistic time-complexity of the decision procedure guaranteed for $(R\_{yes},R\_{no})$.

The theorem can be extended to general construction problems, for example (see **Corollary 3.9**) consider the problem of finding a prime in a large enough interval :

For any fixed $c > 7/12$, on input $N$, find a prime in the interval $[N, N + N^c]$

The randomized algorithm runs in expected polynomial time; no deterministic polynomial time algorithm is known; but if BPP=P such deterministic polynomial time algorithm must exist (because it can be reduced to a BPP-decision problem).


---

