<p>R. Impagliazzo ; G. Tardos <a href="http://ieeexplore.ieee.org/document/63482/" rel="noreferrer">shown</a> 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.</p>

<p>The <a href="http://www.sciencedirect.com/science/article/pii/S0019995885800048" rel="noreferrer">similar situation</a> with collapsing of exponential hierarchy. </p>

CC BY-SA 3.0
2017-02-26T16:09:57.950Z
2017-02-26T18:11:31.183Z
2017-02-26T18:11:31.183Z
Alexey Milovanov
<p>If $\textbf{P}= \textbf{NP}$ then for every language from $\textbf{NP}$ there exists an algorithm of finding a certificate in polynomial time. </p>

<p>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}$? </p>

CC BY-SA 3.0
2017-02-25T19:35:37.740Z
@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?
Alexey Milovanov
CC BY-SA 3.0
2017-02-26T17:46:55.317Z
It seems you've answered your own question with the Impagliazzo Tardos reference. It would be good to post it as an answer.
Joshua Grochow
CC BY-SA 3.0
2017-02-26T22:35:35.090Z
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.
Joshua Grochow
<cc.complexity-theory><complexity-classes>
Finding a certificate if E=NE
Alexey Milovanov
# Finding a certificate if E=NE

(Asked by: username_0 on 2017-02-25)

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}$?

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_0**: @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?  
> **username_1**: It seems you've answered your own question with the Impagliazzo Tardos reference. It would be good to post it as an answer.  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_0 on 2017-02-26. Score: 5

R. Impagliazzo ; G. Tardos [shown](http://ieeexplore.ieee.org/document/63482/) 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](http://www.sciencedirect.com/science/article/pii/S0019995885800048) with collapsing of exponential hierarchy.


---

