We unconditionally prove there exists a promise problem in promise ZSUBEXP that cannot be solved in promise RP.
The proof technique builds upon Kabanets' easy witness method [Kab01] as implemented by Impagliazzo et. al [IKW02], with a separate diagonalization carried out on each of the two alternatives in the win-win argument. Rahul Santhanam showed us a very simple proof that proves a stronger claim. In this revision we give this proof

Rahul Santhanam showed us a very simple proof that proves a stronger claim. In this revision we give this proof

We unconditionally prove there exists a promise problem in promise ZSUBEXP that cannot be solved in promise RP.
The proof technique builds upon Kabanets' easy witness method [Kab01] as implemented by Impagliazzo et. al [IKW02], with a separate diagonalization carried out on each of the two alternatives in the win-win argument. We remark that even though the easy witness method is a key component in many celebrated results in derandomization, we are not aware of any previous unconditional separation like the one we show.

We remark that the result relativizes. We could not prove a similar result for total functions, nor for functions in ZTime(T(n)) for T(n) below a half-exponential function (i.e., T such that T(T(n)) < 2^n).