2
$\begingroup$

The class $C_{1,\epsilon }$ of decision problems solvable by an NP machine such that

  1. If the answer is 'yes,' at least 1/2 and at most $1-\epsilon$ of computation paths reject.

  2. If the answer is 'no,' all computation paths reject.

Is there a name for this class that looks like $RP$?

Is this in $RP$ or $coRP$?

The class $C_{2,\epsilon }$ of decision problems solvable by an NP machine such that

  1. If the answer is 'no,' at least 1/2 and at most $1-\epsilon$ of computation paths accept.

  2. If the answer is 'yes,' all computation paths accept.

Is there a name for this class that looks like $coRP$?

Is this in $RP$ or $coRP$?

What is $C_{1,\epsilon }\cap C_{2,\epsilon}$?

Is it in $ZPP$?

$\endgroup$
  • $\begingroup$ Did you mean to say "if the answer is no, then at least $1/2$ of the computations reject", in the definition of $C_2$? $\endgroup$ – Ariel Dec 22 '17 at 10:33
  • $\begingroup$ Then $C_2$ will be $coRP$. $\endgroup$ – T.... Dec 22 '17 at 10:34
  • $\begingroup$ As you defined it, $C_2=2^{\Sigma^*}$, since a machine which accepts in all paths satisfies both properties for every language. $\endgroup$ – Ariel Dec 22 '17 at 10:35
  • $\begingroup$ $2^{\Sigma^*}$? $\endgroup$ – T.... Dec 22 '17 at 10:36
  • 1
    $\begingroup$ The $\frac{1}{2}$ part doesn't really matter now, and you are actually looking at $RP,coRP$. $\endgroup$ – Ariel Dec 22 '17 at 11:59
3
$\begingroup$

Your class $C_{1,\epsilon}$ is the same as RP. It is clear that everything in $C_{1,\epsilon}$ is in RP. In the other direction, take an RP algorithm for a problem, and amplify its success probability to be $1-\delta$. Now modify it to toss coins and reject with probability $\epsilon$ (or some constant $c > \epsilon$) and only then run. If $\delta$ is small enough, then the overall success probability in the Yes case will be arbitrarily close to $1-\epsilon$.

The same argument shows that $C_{2,\epsilon}=coRP$, and so $C_{1\epsilon} \cap C_{2\epsilon} = ZPP$.

$\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.