<p>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?</p>

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

CC BY-SA 3.0
2013-11-22T19:30:03.777Z
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
CC BY-SA 3.0
2013-11-22T21:10:05.167Z
In addition, as far as I recall, it is a common to conjecture that ZPP=P.
Kaveh
CC BY-SA 3.0
2013-11-22T21:39:10.850Z
If instead of ZPP you ask about RP, polynomial identity testing would be an answer.
Mahdi Cheraghchi
CC BY-SA 3.0
2013-11-22T22:04:08.467Z
@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
CC BY-SA 3.0
2013-11-22T22:26:50.197Z
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
CC BY-SA 3.0
2013-11-22T22:30:11.480Z
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
CC BY-SA 3.0
2013-11-22T23:19:09.260Z
@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
CC BY-SA 3.0
2013-11-23T02:39:23.560Z
If you allow search problems, how about finding a prime between $n$ and $2n$?
Sasho Nikolov
CC BY-SA 3.0
2013-11-23T09:43:22.897Z
@Kaveh: This logic does not work, as Josh pointed out most people also conjecture BPP=P.
domotorp
CC BY-SA 3.0
2013-11-23T09:44:35.573Z
@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
CC BY-SA 3.0
2013-11-24T16:31:56.897Z
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
CC BY-SA 3.0
2013-12-05T00:37:00.207Z
@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
<cc.complexity-theory><complexity-classes><randomness>
Is there a problem in ZPP not yet in P?
domotorp
# Is there a problem in ZPP not yet in P?

(Asked by: username_0 on 2013-11-22)

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.

**Tags:** cc.complexity-theory, complexity-classes, randomness
> **Comments:**
> **username_1**: 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.  
> **username_1**: In addition, as far as I recall, it is a common to conjecture that ZPP=P.  
> **username_2**: If instead of ZPP you ask about RP, polynomial identity testing would be an answer.  
> **username_3**: @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.  
> **username_4**: I wonder if there are generalizations of the primality problem itself for which the ZPP algorithm (Adleman–Huang) works, but AKS does not.  
> **username_3**: 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.  
> **username_1**: @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).  
> **username_5**: If you allow search problems, how about finding a prime between $n$ and $2n$?  
> **username_0**: @Kaveh: This logic does not work, as Josh pointed out most people also conjecture BPP=P.  
> **username_0**: @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.  
> **username_6**: 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/  
> **username_3**: @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.  

---

## 0 answers

