Finding a certificate if E=NE
R. Impagliazzo ; G. Tardos shown that there exists  an oracle  relative to which
$\textbf{E} = \textbf{NE}$ , yet there is an exponential-type search problem
that requires doubly exponential randomized time.

The similar situation with collapsing of exponential hierarchy.