17
$\begingroup$

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

$\endgroup$
  • 6
    $\begingroup$ Doesn't the time hierarchy theorem guarantees the existence of such problems? $\endgroup$ – R B Nov 13 '15 at 11:46
  • $\begingroup$ @RB Thank you for your reply. Do you believe time hierarchy can collapse? I am expecting some natural examples that can be solved in quasi-polynomial time but not in polynomial time. $\endgroup$ – Rupei Xu Nov 13 '15 at 11:52
  • 3
    $\begingroup$ @RupeiXu It is a known fact that it can't collapse. $\endgroup$ – Tom van der Zanden Nov 13 '15 at 12:05
  • 3
    $\begingroup$ @RupeiXu Your question would be interesting if you are looking for natural problem. $\endgroup$ – Mohammad Al-Turkistany Nov 13 '15 at 13:11
  • 3
    $\begingroup$ Minimum dominating set in tournments is in QP. It can not be in P unless the ETH is false. $\endgroup$ – Mohammad Al-Turkistany Nov 13 '15 at 20:49
21
$\begingroup$

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.

$\endgroup$
19
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.