Is there a natural problem in quasi-polynomial time, but not in polynomial time? László Babai recently proved that 
the Graph Isomorphism problem is in quasipolynomial time.
See also his
talk at University of Chicago,
note from the talks by Jeremy Kun
GLL post 1,
GLL post 2,
GLL post 3.

According to Ladner’s theorem, 
if $P \neq NP$, then $NPI$ is not empty, 
i.e. $NP$ contains problems that are neither in $P$ nor $NP$-complete. 
However, the language constructed by Ladner is artificial and 
not a natural problem.
No natural problem is known to be in $NPI$ 
even conditionally under $P \neq NP$. 
But some problems are believed to be good candidates for $NPI$, 
such as Factoring integers and GI.

We may think that with Babai's result,
there might be a polynomial time algorithm for GI.
Many experts believe that $NP \not\subseteq QP = DTIME(n^{poly\log n})$.

There are some problems for which we know quasi-polynomial time algorithms, 
but no polynomial time algorithm is known. 
Such problems arise in approximation algorithms; 
a famous example is the directed Steiner tree problem, 
for which there is a quasi-polynomial time approximation algorithm 
achieving an approximation ratio of $O(\log^3 n)$ 
($n$ being the number of vertices). 
However, showing the existence of such a polynomial time algorithm 
is an open problem.

My question: 


  Do we know any natural problems which are in $QP$ but not in $P$?
There has, in fact, been quite a lot of recent works on proving quasi-polynomial running time lower bound for computational problems, mostly based on the exponential time hypothesis. Here are some results for problems that I consider quite natural (all results below are conditional on ETH):


Aaronson, Impagliazzo and Moshkovitz [1] show a quasi-polynomial time lower bound for dense constraint satisfaction problems (CSPs). Note that the way CSP is defined in this paper allows the domain to be polynomially large, as the case where the domain is small is known to have a PTAS.
Braverman, Ko and Weinstein [2] prove a quasi-polynomial time lower bound for finding $\epsilon$-best $\epsilon$-approximate Nash equilibrium, which matches Lipton et al.'s algorithm [3].
Braverman, Ko, Rubinstein and Weinstein [4] show a quasi-polynomial time lower bound for approximating densest $k$-subgraph with perfect completeness (i.e. given a graph that contains a $k$-clique, finds a subgraph of size $k$ that is $(1 - \epsilon)$-dense for some small constant $\epsilon$). Again, there is a quasi-polynomial time algorithm for the problem (Feige and Seltser [5]).


References


AM with multiple Merlins. In Computational Complexity (CCC), 2014 IEEE 29th Conference on, pages 44–55, June 2014.
Mark Braverman, Young Kun Ko, and Omri Weinstein. Approximating the best nash equilibrium in $n^{o(log n)}$-time breaks the exponential time hypothesis. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’15, pages 970–982. SIAM, 2015.
Richard J. Lipton, Evangelos Markakis, and Aranyak Mehta. Playing large games using simple strategies. In Proceedings of the 4th ACM Conference on Electronic Commerce, EC ’03, pages 36–41, New York, NY, USA, 2003. ACM.
Mark Braverman, Young Kun-Ko, Aviad Rubinstein, and Omri Weinstein. ETH hardness for Densest-$k$-Subgraph with perfect completeness. Electronic Colloquium on Computational
Complexity (ECCC), 22:74, 2015.
U. Feige and M. Seltser. On the densest $k$-subgraph problems. Technical report, 1997.