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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.