The title pretty much says it all, but to explain how I got there:

I think, that one of the reasons we are unable to prove or disprove , but mainly disprove $P=NP$ (and yes, I was provoked by the discussed recent proof about $P$ vs $NP$) is because we can't take some superpolynomial subexponential problem and reduce it to some $NP$-complete, because in this "grey" area above $P$ are two types of problems - ones in $NP$ and ones not in $NP$. But I know little to nothing about these problems, nor what is the state-of-the-art of current scientific community knowledge, but I just wonder whether there is a problem known to have this property.

I\ve been going through similar question to this one, but I could not deduce from posts there answer to this question.

EDIT: It is irrelevant whether the language is mathematically artificial or describes something "natural", as long as one can prove it is in $QP$ and not in $NP$, or at least give a very convincing argument for it.

  • 1
    $\begingroup$ So I guess the answer to my original question is that there is no known problem to be quasi-polynomial and not in NP. $\endgroup$ – TStancek Aug 17 '17 at 11:59
  • 3
    $\begingroup$ There are obnoxious solutions to this. E.g., take the following problem {$(M,x)$ : $M$ is a turing machine that accepts on input $x$ in at most $n^{\log n}$ steps, where $n := |M| + |x|$ }$. $\endgroup$ – Noah Stephens-Davidowitz Aug 17 '17 at 13:39
  • 2
    $\begingroup$ Let us assume that there is such a problem $\pi$, in $QP$ but not in $NP$. 1. If $\pi$ is $NP$-hard, then $NP \subseteq QP$, which breaks the ETH. 2. If $\pi \in polyL$, then $polyL$ is not included in $P$. 3. Otherwise, $\pi \in QP \setminus polyL$. By padding, we build $\pi' \in P \setminus L$. All three consequences above are unknown. If your answer has a positive answer, I suggest to look around one of those three problems (ETH, $polyL$ vs $P$, $P$ vs $L$). $\endgroup$ – Boson Aug 21 '17 at 21:37
  • 2
    $\begingroup$ $\mathsf{QP\not\subset NP\Rightarrow NP\subsetneq EXP}$, which is open problem. $\endgroup$ – rus9384 Aug 31 '17 at 11:05
  • 2
    $\begingroup$ I can't help you here as it is major opened problem. Even such a construction is pointless, if classes are equal. $\endgroup$ – rus9384 Aug 31 '17 at 12:37

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.