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

<p>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.</p>

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

<p>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.</p>

CC BY-SA 3.0
2017-08-17T11:59:52.687Z
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
CC BY-SA 3.0
2017-08-17T13:39:02.997Z
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
CC BY-SA 3.0
2017-08-17T13:47:57.263Z
@NoahStephens-Davidowitz Well, my original question asked for problems that are known to be outside NP, but user Gamow edited it to this, and since I am not expert, I considered that to be a better question. You just showed, it is probably a worse one.
TStancek
CC BY-SA 3.0
2017-08-21T21:37:12.153Z
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
CC BY-SA 3.0
2017-08-30T11:32:55.673Z
@NoahStephens-Davidowitz I've been thinking of something  similar, but inspired by exp-complete problem, where the unsolvability in smaller time is due to the need to go through all posibilities and collect the data. So my proposal was a language of words, that when represented as Turing machines on a given UTM, accept in a polynomial time more than half of all the words of such length, that there are quasipolynomially many of them to the length of the code of the Turing machine. So, basicallyt words have length quasipolynomial to the logarithm of the length of the input TM's code.
TStancek
CC BY-SA 3.0
2017-08-31T04:57:35.723Z
You're not going to find a problem that's KNOWN not to be in NP because this would imply complexity-theoretic results that are unknown at the moment, as rus9384 and Boson pointed out. The language that I mentioned has the nice property that it's clearly at least as hard as any language that's decidable in $n^{\log n}$ time, though it's obviously obnoxious and unnatural. I don't think you're likely to find "natural" examples because (1) most languages that we discover "naturally" are in NP; and (2) most languages that we discover "naturally" do not seem to lie in QP\P.
Noah Stephens-Davidowitz
CC BY-SA 3.0
2017-08-31T05:57:18.083Z
@NoahStephens-Davidowitz It is sufficient to prove it is in QP and not in NP, whether it is "natural" or not is irrelevant. I rather add it to the body of the question.
TStancek
CC BY-SA 3.0
2017-08-31T06:48:10.877Z
Perhaps change the title from "not known to be in NP" to "known to not be in NP"
Thomas Steinke
CC BY-SA 3.0
2017-08-31T07:19:43.260Z
@Thomas it originally was, but then someone made an edit approved by others to name it this way. I can probably change it back though
TStancek
CC BY-SA 3.0
2017-08-31T11:05:14.437Z
$\mathsf{QP\not\subset NP\Rightarrow NP\subsetneq EXP}$, which is open problem.
rus9384
CC BY-SA 3.0
2017-08-31T11:13:38.237Z
@rus9384 so there is no known problem outside $PSPACE$ in $EXPTIME$?
TStancek
CC BY-SA 3.0
2017-08-31T11:34:39.737Z
@rus9384 Please bare in mind that I am an amateur here, but shouldn't a language  $L=<T,W>$ checking whether this Turing machine $T$ uses more than $n^{log(n)}$ space under $10^n$ steps, where $n=|W|$, satisfy such condition?To simulate the TM $T$ reaching such a number of used cells, the universal TM must also use this many and it is not outside EXPTIME, becuase if it takes too long, the machine ends. But I guess it is an open question, whether there is a possibility of deducing such property without using that many cells by using more steps, or just somehow with fewer cells.
TStancek
CC BY-SA 3.0
2017-08-31T12:35:01.087Z
@rus9384 Not sure now, but I am asking whether these two are simultaneously true: DTISP(exp,qpoly) $\subseteq$ EXPTIME (which it should by definition) and DTISP(exp,qpoly) $\neq$ DTISP(exp, poly). So yeah, $QPSPACE$ language has the potential to run in a much more steps, but that is not my aim.I tried to present a language decidable in EXPTIME, that is not possible to decide using less than $qpoly$ space, forcing it outside PSPACE, yet being in EXPTIME. But, that construction is of course not a proof, just a hunch why it might be true.
TStancek
CC BY-SA 3.0
2017-08-31T12:37:59.437Z
I can't help you here as it is major opened problem. Even such a construction is pointless, if classes are equal.
rus9384
CC BY-SA 3.0
2017-08-31T13:34:12.960Z
Also we know that $\mathsf{QP\neq PSPACE}$. You can use time hierarchy theorem for the proof.
rus9384
<time-complexity><polynomial-time>
Do we know some quasi-polynomial problem that is known to not be in NP?
TStancek
# Do we know some quasi-polynomial problem that is known to not be in NP?

(Asked by: username_0 on 2017-08-17)

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.

**Tags:** time-complexity, polynomial-time
> **Comments:**
> **username_0**: So I guess the answer to my original question is that there is no known problem to be quasi-polynomial and not in NP.  
> **username_1**: 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|$  }$.  
> **username_0**: @NoahStephens-Davidowitz Well, my original question asked for problems that are known to be outside NP, but user Gamow edited it to this, and since I am not expert, I considered that to be a better question. You just showed, it is probably a worse one.  
> **username_2**: 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$).  
> **username_0**: @NoahStephens-Davidowitz I've been thinking of something  similar, but inspired by exp-complete problem, where the unsolvability in smaller time is due to the need to go through all posibilities and collect the data. So my proposal was a language of words, that when represented as Turing machines on a given UTM, accept in a polynomial time more than half of all the words of such length, that there are quasipolynomially many of them to the length of the code of the Turing machine. So, basicallyt words have length quasipolynomial to the logarithm of the length of the input TM's code.  
> **username_1**: You're not going to find a problem that's KNOWN not to be in NP because this would imply complexity-theoretic results that are unknown at the moment, as rus9384 and Boson pointed out. The language that I mentioned has the nice property that it's clearly at least as hard as any language that's decidable in $n^{\log n}$ time, though it's obviously obnoxious and unnatural. I don't think you're likely to find "natural" examples because (1) most languages that we discover "naturally" are in NP; and (2) most languages that we discover "naturally" do not seem to lie in QP\P.  
> **username_0**: @NoahStephens-Davidowitz It is sufficient to prove it is in QP and not in NP, whether it is "natural" or not is irrelevant. I rather add it to the body of the question.  
> **username_3**: Perhaps change the title from "not known to be in NP" to "known to not be in NP"  
> **username_0**: @Thomas it originally was, but then someone made an edit approved by others to name it this way. I can probably change it back though  
> **username_4**: $\mathsf{QP\not\subset NP\Rightarrow NP\subsetneq EXP}$, which is open problem.  
> **username_0**: @rus9384 so there is no known problem outside $PSPACE$ in $EXPTIME$?  
> **username_0**: @rus9384 Please bare in mind that I am an amateur here, but shouldn't a language  $L=<T,W>$ checking whether this Turing machine $T$ uses more than $n^{log(n)}$ space under $10^n$ steps, where $n=|W|$, satisfy such condition?To simulate the TM $T$ reaching such a number of used cells, the universal TM must also use this many and it is not outside EXPTIME, becuase if it takes too long, the machine ends. But I guess it is an open question, whether there is a possibility of deducing such property without using that many cells by using more steps, or just somehow with fewer cells.  
> **username_0**: @rus9384 Not sure now, but I am asking whether these two are simultaneously true: DTISP(exp,qpoly) $\subseteq$ EXPTIME (which it should by definition) and DTISP(exp,qpoly) $\neq$ DTISP(exp, poly). So yeah, $QPSPACE$ language has the potential to run in a much more steps, but that is not my aim.I tried to present a language decidable in EXPTIME, that is not possible to decide using less than $qpoly$ space, forcing it outside PSPACE, yet being in EXPTIME. But, that construction is of course not a proof, just a hunch why it might be true.  
> **username_4**: I can't help you here as it is major opened problem. Even such a construction is pointless, if classes are equal.  
> **username_4**: Also we know that $\mathsf{QP\neq PSPACE}$. You can use time hierarchy theorem for the proof.  

---

## 0 answers

