1
$\begingroup$

$\mathsf{RP}$ can be deterministically defined as:

A language $L\in\mathsf{RP}$ iff there exists a polynomial $p$ and deterministic Turing machine $M$, such that:

  • $M$ runs for polynomial time $p$ on all inputs,
  • $\forall x \in L$, the fraction of strings $y$ of length $p(\vert x\vert)$ which satisfy $M(x, y) = 1$ is greater than or equal to $\frac1 2$,
  • $\forall x \not\in L$, and all strings $y$ of length $p(|x|)$, $M(x, y) = 0$

In contrast, $\mathsf{UP}$ can be defined as:

A language $L\in \mathsf{UP}$ if there exists a two-input algorithm $A$ and a constant $c$ such that:

  • $x \in L\Rightarrow\exists! y:${$\vert y\vert = \mathcal O(\vert x\vert^c),A(x,y) = 1$},
  • $x \not\in L\Rightarrow\not\exists y:${$\vert y\vert = \mathcal O(\vert x\vert^c), A(x,y) = 1$},
  • algorithm $A$ verifies $L$ in polynomial time.

Therefore, a satisfying $L\in\mathsf{RP\cap UP}$ would have to satisfy both:

  • the fraction of strings $y$ of length $p(\vert x\vert)$ which satisfy $M(x, y) = 1$ is greater than or equal to $\frac1 2$,
  • $\exists! y:${$\vert y\vert = \mathcal O(\vert x\vert^c),A(x,y) = 1$}

It seems these are mutually exclusive requirements. So, how does it happen that $\mathsf P$, a class containing satisfying languages, contains only such languages?

$\endgroup$

1 Answer 1

2
$\begingroup$

The $\mathsf{RP}$ machine and the $\mathsf{UP}$ machine don't have to be the same. That is, there might be one machine which shows that $L \in \mathsf{RP}$, and another one which shows that $L \in \mathsf{UP}$.

As an example, every language in $\mathsf{P}$ lies in $\mathsf{RP} \cap \mathsf{UP}$. The easiest way to see this is to take the advice string to be empty, but if you insist that the advice string have size $|x|$, say, then you can construct an $\mathsf{RP}$ machine which ignores the advice and just runs the $\mathsf{P}$ machine, and a $\mathsf{UP}$ machine which runs the $\mathsf{P}$ machine and only accepts if the advice is the all-zero string.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.