27
$\begingroup$

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

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ To be precise, what is the decision version of these problems you have in mind? Thanks. $\endgroup$ – usul Dec 31 '14 at 4:42
  • $\begingroup$ @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. $\endgroup$ – Peter Shor Jan 1 '15 at 14:17
  • $\begingroup$ 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]$?" $\endgroup$ – usul Jan 1 '15 at 20:57
  • $\begingroup$ @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 to prove it works. $\endgroup$ – Peter Shor Jan 22 '15 at 22:22
  • $\begingroup$ Ok, sure/fine. I think I agree with Kaveh's comment in this question that a natural corresponding decision problem is, given $a,b$, is there a prime in $[a,b]$? $\endgroup$ – usul Jan 23 '15 at 7:28
10
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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

$\endgroup$

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.