Problems in $\mathsf{BPP}$ not known to be in $\mathsf P$?

Question

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 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)!

Answer 1

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.

Answer 2

There is a particular use of randomness that is fairly common in parameterized complexity, which involves either the isolation lemma, or the Schwartz-Zippel 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 (author's 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). (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 3

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

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