# Do we know some quasi-polynomial problem that is known to not be in NP?

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.

• So I guess the answer to my original question is that there is no known problem to be quasi-polynomial and not in NP. – TStancek Aug 17 '17 at 11:59
• 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|$ }$. – Noah Stephens-Davidowitz Aug 17 '17 at 13:39 • 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$). – Boson Aug 21 '17 at 21:37 •$\mathsf{QP\not\subset NP\Rightarrow NP\subsetneq EXP}\$, which is open problem. – rus9384 Aug 31 '17 at 11:05
• I can't help you here as it is major opened problem. Even such a construction is pointless, if classes are equal. – rus9384 Aug 31 '17 at 12:37