# Finding a certificate if E=NE

If $\textbf{P}= \textbf{NP}$ then for every language from $\textbf{NP}$ there exists an algorithm of finding a certificate in polynomial time.

Assume that $\textbf{E} = \textbf{NE}$. Is it true that there is an algorithm of finding a certificate in exponential time for every language from $\textbf{NE}$?

• @JoshuaGrochow I know the following proof for $\textbf{P}=\textbf{NP}$: let $L \in \textbf{NP}$. Consider $L'= \{ (x, y) \mid x \in L, y \text{ is a prefix of a certificate for } x \}$. Since $L' \in \textbf{NP}=\textbf{P}$ and $|y|$ bounded by a polynomial we have a polynomial time algorithm finding a certificate. However, for $\textbf{E}=\textbf{NE}$ the length of $y$ will be exponential, so this reasoning gives a double-exponential algorithm, isn't it? Feb 25 '17 at 19:35
• It seems you've answered your own question with the Impagliazzo Tardos reference. It would be good to post it as an answer. Feb 26 '17 at 17:46
• Bellare & Goldwasser show a related result: if doubly-exponential time isn't equal to nondeterministic doubly-exponential time, then there is a problem in NP whose search version doesn't reduce to its decision version. Feb 26 '17 at 22:35

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.