Primality was a nice problem that was in ZPP but was not known to be in P. Is there a (preferably simple to state) problem of which we can prove that it is in ZPP but we do not know whether it is in P or not?

I know ZPP=EXP might hold and so on, I want a problem surely in ZPP that is not surely in P.

  • 3
    $\begingroup$ Surely the last sentence might be confusing since one interpretation would be that you are asking for their separation whereas you are probably looking for conjectured candidates. Recalling that the number of problems conjectured to be between P and NP are so small there are probably no problem conjectured to be in ZPP-P. $\endgroup$
    – Kaveh
    Nov 22 '13 at 19:30
  • 4
    $\begingroup$ @Kaveh: It is also a common conjecture that BPP=P, yet we have other interesting questions on this site such as problems known to be in BPP but not known to be in RP union coRP (cstheory.stackexchange.com/questions/11425/…). Also, although the number of problems conjectured to be truly NP-intermediate is a couple of orders of magnitudes smaller than the number known to be in P or NP-complete, I wouldn't characterize it as "so small": cstheory.stackexchange.com/questions/79/…. $\endgroup$ Nov 22 '13 at 22:04
  • 2
    $\begingroup$ For the (nearly-)linear time analog of your question, I believe that there are many algorithms on permutation groups that are known to be in $\mathsf{ZPTIME}[\tilde{O}(n)]$ (that is, Las Vegas nearly-linear time, where the "nearly-" means up to poly-logarithmic factors) that are not known to be in $\mathsf{DTIME}[\tilde{O}(n)]$. See, e.g., the book "Permutation Group Algorithms" by A. Seress. $\endgroup$ Nov 22 '13 at 22:30
  • 4
    $\begingroup$ If you allow search problems, how about finding a prime between $n$ and $2n$? $\endgroup$ Nov 23 '13 at 2:39
  • 1
    $\begingroup$ @Kaveh: This logic does not work, as Josh pointed out most people also conjecture BPP=P. $\endgroup$
    – domotorp
    Nov 23 '13 at 9:43

The Problem:

Input: $\;\;$ a tuple that parses as $\:\langle \hspace{.04 in}p,\hspace{-0.03 in}y,\hspace{-0.03 in}i\hspace{.02 in}\rangle$

if $p$ is prime and $y$ is a quadratic residue modulo $p$, $\;$ then the $\hspace{.02 in}i\hspace{.03 in}$th$\hspace{.01 in}$ bit of the
non-negative integer $x$ that satisfies $\;\;\; x^{\hspace{.02 in}2} \equiv y \; \pmod p\;\;\;$ and $\;\; 2\hspace{-0.04 in}\cdot \hspace{-0.04 in}x \: \leq \: p \;\;$,
else 0

According to the wiki article, that problem is in ZPP but is not known to be in P.

  • 2
    $\begingroup$ This is a nice answer, but I was wondering why did you format it in this odd way? It doesn't really matter but I find it distracting. $\endgroup$ Nov 25 '13 at 1:09
  • $\begingroup$ I tried to put things that go together closer together. $\:$ $\endgroup$
    – user6973
    Nov 25 '13 at 1:37
  • 1
    $\begingroup$ I guess primes and commas do not go together then :) $\endgroup$ Nov 25 '13 at 4:13
  • 1
    $\begingroup$ It's inequalities and [commas that are not part of the inequality] that do not go together. $\hspace{.52 in}$ $\endgroup$
    – user6973
    Nov 25 '13 at 4:35
  • 1
    $\begingroup$ @RickyDemer even your comments are formatted in a odd way. $\endgroup$ Nov 25 '13 at 16:38

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.