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

  • 4
    $\begingroup$ @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? $\endgroup$ Feb 25 '17 at 19:35
  • $\begingroup$ It seems you've answered your own question with the Impagliazzo Tardos reference. It would be good to post it as an answer. $\endgroup$ Feb 26 '17 at 17:46
  • $\begingroup$ 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. $\endgroup$ 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.

The similar situation with collapsing of exponential hierarchy.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.