Given an arbitrary language $L$ with an algorithm $A$ that places $L$ in $co-RP$ what other properties does the Algorithm $A$ need to have to so that $L$ is in $P$?

For example:

Considering $L$ is in $co-RP$ we have a guarantee that:

if $x \in L$ then $A$ accepts $x$ guaranteed $(P(A(x)=1) = 1)$

if $x \not\in L$ then $A$ accepts $x$ with a propability $f(n)$ $(P(A(x)=1) = f(n))$ with $n = |x|$ and $f(n) \geq 0$

What property does $f$ need to have so that $L$ is in $P$?

As $P \subseteq ZPP$ and $ZPP = RP \cap co-RP$ there needs to be a property to $f$ that places $L$ also in $RP$. As such there needs to be a way to construct an algorithm $B$ for $L$ that discards $x \not\in L$ guaranteed in polynomial time. Under what conditions for $A$ is this possible? For what $f$ is this the case? Is there any other property $A$ needs to have so that $L$ is in $P$?

  • 2
    $\begingroup$ "What properties" is very broad; there are many ways one could write down some possible properties (e.g., one property is that there has to exist a polynomial-time algorithm for recognizing $L$). Can you narrow things down at all? What kinds of properties are you thinking of, or would be useful? Do you have any particular reason to expect there to be any nice set of properties that does what you want? $\endgroup$ – D.W. Apr 16 '19 at 19:57
  • $\begingroup$ I was hoping for a very general set of properties that HAVE to exist and I did not want to set any boundries or preconceptions that might narrow down this generalized set of properties like "$A$ has a polynomial runtime with upper bound on words of length $n$: $p(n)$". Though I can see that with such a precondition the set can be narrowed down to certain cases and not a huge list of "if that - then that, if that - then that, etc." $\endgroup$ – salbeira Apr 16 '19 at 20:08
  • 1
    $\begingroup$ I'm not sure what you mean. To be in P, it needs to be decidable by a deterministic Turing machine in polynomial time. End of. $\endgroup$ – David Richerby Apr 17 '19 at 10:43
  • $\begingroup$ When you are only given a randomised algorithm with properties placing L in co-RP how can questions be asked to make you prove that L is in P? $\endgroup$ – salbeira Apr 17 '19 at 11:06

Considering from my comment that there exists an upper bound to the runtime of $A$: $p(n)$ then there are only $2^{p(n)}$ possible ways a coin-flip of a randomized algorithm can manipulate the outcome of the result.

If the error propability of $A$ I described as $f$ is a fraction with part $\frac{g(n)}{2^{p(n)}}$ then creating a deterministic program that runs $g(n)$ many times plus one different paths of a possible computation of $A$ it is guaranteed that at least one of these paths would have identified the false positive as false.

Therefore we can skip the journey through $RP$ into $ZPP$ and can argue that if $g$ is a polynomial function we need to run $g(n) + 1$ times the polynomial Algorithm $A$ resulting in a polynomial runtime of $(g(n)+1) \cdot p(n)$ that deterministically solves $x\in L$ or $x \not\in L$ with an error propability of $0$, therefore placing $L$ in $P$.

This is but one case where, given a randomized algorithm that places a language $L$ clearly in $co-RP$ places $L$ also in $P$.

| cite | improve this answer | |

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.