12

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.

domotorp
  • 13,931
  • 37
  • 93
  • 3
    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. – Kaveh Nov 22 '13 at 19:30
  • In addition, as far as I recall, it is a common to conjecture that ZPP=P. – Kaveh Nov 22 '13 at 21:10
  • If instead of ZPP you ask about RP, polynomial identity testing would be an answer. – Mahdi Cheraghchi Nov 22 '13 at 21:39
  • 4
    @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 (http://cstheory.stackexchange.com/questions/11425/problem-in-bpp-but-not-known-to-be-in-rp-or-co-rp). 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": http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc. – Joshua Grochow Nov 22 '13 at 22:04
  • I wonder if there are generalizations of the primality problem itself for which the ZPP algorithm (Adleman–Huang) works, but AKS does not. – Alessandro Cosentino Nov 22 '13 at 22:26
  • 2
    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. – Joshua Grochow Nov 22 '13 at 22:30
  • @Josh, my point: we shouldn't expect finding problems that are conjectured to be in ZPP-P as long as we conjecture ZPP=P (i.e. as it seems to me that is what domotorp is looking for in the last sentence of the question). – Kaveh Nov 22 '13 at 23:19
  • 4
    If you allow search problems, how about finding a prime between $n$ and $2n$? – Sasho Nikolov Nov 23 '13 at 02:39
  • 1
    @Kaveh: This logic does not work, as Josh pointed out most people also conjecture BPP=P. – domotorp Nov 23 '13 at 09:43
  • @Sasho: Yes, for search problems that would be a good example but I really want what I asked for - my main goal is to give an example for students. – domotorp Nov 23 '13 at 09:44
  • 1
    This also doesn't seem to answer your question, but the 'Bellagio' or 'pseudo-deterministic' algorithms of Gat-Goldwasser are relevant. These are randomized algorithms to solve an NP search problem, that w.h.p. return some fixed value (but may occasionally give another value or fail to solve the search problem at all). http://eccc.hpi-web.de/report/2011/136/ – Andy Drucker Nov 24 '13 at 16:31
  • 1
    @Kaveh: Until we have a proof, I think it's healthy, when believing a conjecture such as ZPP=P, to keep in mind potential counterexamples. Both because the conjecture might turn out to be false, and because any proof of the conjecture must somehow take care of all the potential counterexamples. – Joshua Grochow Dec 05 '13 at 00:37

1 Answers1

13

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$

Output:
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.