Is there a natural problem in quasi-polynomial time, but not in polynomial time?

Question

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$?

Answer 1

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

1. AM with multiple Merlins. In Computational Complexity (CCC), 2014 IEEE 29th Conference on, pages 44–55, June 2014.

2. 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.

3. 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.

4. 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.

5. U. Feige and M. Seltser. On the densest $k$-subgraph problems. Technical report, 1997.

Answer 2

Megiddo and Vishkin proved that Minimum dominating set in tournaments is in $QP$. They showed that tournament dominating set has P-time algorithm iff SAT has subexponential time algorithm. Therefore, tournament dominating set problem can not be in $P$ unless the ETH is false.

It is very interesting to note that the exponential time hypothesis simultaneously implies that tournament dominating set can not have polynomial time algorithms and it can not be $NP$-complete. In other words, ETH implies that tournament dominating set is in $NP$-intermediate.

Woeginger suggests a candidate problem solvable in quasi-polynomial time and probably does not have polynomial time algorithms: Given $n$ integers, can you select $\log n$ of them that add up to $0$?

Answer 3

Computing VC dimension seems unlikely to be in polynomial time, but has a quasipolynomial time algorithm.

Also, it seems hard to detect a planted clique of size $O(\log n)$ in a random graph, but one can be found in quasipolynomial time; though the nature of this promise problem is somewhat different than the others mentioned.

Answer 4

If the exponential time hypothesis is correct (or even weaker versions), then one can not solve 3SAT for instances with polyglog number of variables in polynomial time. Of course, quasi-polynomial time can solve such instances readily.

While we know that there must be problems in time class $T(n ) * \log n$ which is not in $T(n)$, for any $T(n)$, this is not a useful natural problem (this is a standard result in complexity). In any case, finding a problem that is in QP but not in P would be a huge result. We currently dont even know of natural problems in NP that require more than, say, quadratic time in the general RAM model. Because lower bounds are really really really hard. Thus, the resort to the ETH, unique game conjecture, praying, and proving that problems are NP-Complete.

Answer 5

Solving Parity games has recently been shown to be in QP: https://www.comp.nus.edu.sg/~sanjay/paritygame.pdf

Parity games arise naturally in many formal verification contexts, such as LTL synthesis and $\mu$-calculus satisfiabiability.

Parity games were known to be in $NP\cap coNP$, and even in $UP\cap coUP$. In addition, there have been repeated improvements in the exponent of a deterministic algorithm for them, over the past two decades (see the introduction in the link above for a survey).

However, the recent paper above made a significant jump to QP. It is still unknown whether these games are in P.

Answer 6

In Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems by Aram Harrow, Saeed Mehraban, and Mehdi Soleimanifar

a quasi-polynomial time classical algorithm that estimates the partition function of quantum many-body systems at temperatures above the thermal phase transition point

is presented.

Not much can be said here about the "but not in polynomial time" part of the question. It may even be likely that a polynomial time algorithm will be found later, given the history of previous work, see below.

How is "estimating the partition function" related to approximation algorithms? Previous work (p. 11):

There is a recent conceptually different approach to estimating the partition function, which is the basis of this work. This approach views the partition function as a high-dimensional polynomial and uses the truncated Taylor expansion to extend the solution at a computationally easy point to a non-trivial regime of parameters. Since its introduction [Bar16a], this method has been used to obtain deterministic algorithms for various interesting problems such as the ferromagnetic and antiferromagnetic Ising models [LSS19b, PR18] on bounded graphs.

includes

[LSS19b] Jingcheng Liu, Alistair Sinclair, and Piyush Srivastava. The Ising partition function: zeros and deterministic approximation. Journal of Statistical Physics, 174(2):287–315, 2019. arXiv:1704.06493

which mentions the following in tis section on related work:

In a parallel line of work, Barvinok initiated the study of Taylor approximation of the logarithm of the partition function, which led to quasipolynomial time approximation algorithms for a variety of counting problems [6, 7, 9, 10]. More recently, Patel and Regts [41] showed that for several models that can be written as induced subgraph sums, one can actually obtain an FPTAS from this approach.

[41] V. Patel and G. Regts. Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials. SIAM J. Comput., 46(6):1893–1919, Dec. 2017. arXiv:1607.01167

In conclusion, "estimating the partition function" is closely related to approximation algorithms, and there have been quasipolynomial time approximation algorithms for a variety of counting problems, and for some of those FPTAS have been obtained. So overall, this class of problems related to the partition function both seems to produce quasipolynomial time approximation algorithms, but often later improvements achieve polynomial time.

Answer 7

Discrete Log over subgroups of finite fields of fixed characteristic (meaning $\mathbb{F}_{p^n}$ as $n\to\infty$) is known to be in quasi-polynomial time, see Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic by Thorsten Kleinjung and Benjamin Wesolowski. The hardness of (classical) DL-based cryptography is based on the assumption that a suitable average-case variant of this problem (say the computational diffie-hellman problem) is not in $P$.