Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR20-059 | 16th April 2020 18:25

Pr-ZSUBEXP is not contained in Pr-RP


Authors: Gonen Krak, Noam Parzanchevski, Amnon Ta-Shma
Publication: 27th April 2020 08:27
Downloads: 171


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

ISSN 1433-8092 | Imprint