# Is there a name for this class?

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$?

• 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$? – Ariel Dec 22 '17 at 10:33
• Then $C_2$ will be $coRP$. – T.... Dec 22 '17 at 10:34
• As you defined it, $C_2=2^{\Sigma^*}$, since a machine which accepts in all paths satisfies both properties for every language. – Ariel Dec 22 '17 at 10:35
• $2^{\Sigma^*}$? – T.... Dec 22 '17 at 10:36
• The $\frac{1}{2}$ part doesn't really matter now, and you are actually looking at $RP,coRP$. – Ariel Dec 22 '17 at 11:59

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