<p>Group Isomorphism! Although Ricky Demer gave lots (though certainly not all) details on this, there is an important point I want to highlight, esp. given the stated motivation for the question, namely:</p>

<blockquote>
  <p><strong>Putting Group Isomorphism into $\mathsf{P}$ is a key obstacle to putting Graph Isomorphism into $\mathsf{P}$</strong></p>
</blockquote>

<p>Group Isomorphism (when given by multiplication tables) reduces to Graph Isomorphism, so the above was technically always true. But when Graph Iso was way up at $2^{\tilde{O}(\sqrt{n})}$ it was so far from Group Iso's $2^{(\log n)^2}$ that there were clearly other obstacles in the way. If Graph Iso is in time $2^{(\log n)^{O(1)}}$, Group Isomorphism is then a much more immediately relevant obstacle to putting Graph Isomorphism into $\mathsf{P}$. In particular, this would suggest that Babai's algorithm handles much [1] of the combinatorics of GI, and the problem is now down to hard algebra. (Not that there's not hard algebra in GI, but GroupIso is <em>by definition</em> about algebra.) </p>

<p>[1] I won't say "all" of the combinatorics, because the exponent in Babai's algorithm is most likely $&gt; 2$, which would still leave a gap between GI and GroupIso. Also because there may still be some combinatorics sitting inside the algebra of GroupIso...</p>

CC BY-SA 3.0
2015-11-17T07:09:19.520Z
Nice. Your answer is perfectly suitable as an answer to this post: http://cstheory.stackexchange.com/questions/32160/what-evidence-is-there-that-graph-isomorphism-is-not-in-p
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-11-17T16:09:06.557Z
@MohammadAl-Turkistany: Only if you think that Group Iso isn't in P... Also, Thomas Kimpel's answer to that question already sort of hits on this point (but at the time, as I said, GI was so far from GroupIso that there could've in principle been other reasons for it not to be in P).
Joshua Grochow
CC BY-SA 3.0
2015-11-17T01:03:15.993Z
2015-11-17T01:03:15.993Z
Joshua Grochow
<p>Solving the <a href="https://en.wikipedia.org/wiki/Planted_clique">planted clique problem</a> of distinguishing a uniformly random graph from the union of a random graph and a clique (of size intermediate between $2\log_2 n$ and $\sqrt n$), with success probability bounded away from 1/2. It differs from your ETH-violating example of finding polylog-sized cliques in arbitrary graphs, because this is an average-case problem not a worst-case one.</p>

CC BY-SA 3.0
2015-11-17T00:35:13.900Z
2015-11-17T00:35:13.900Z
David Eppstein
<p>Approximating the Directed Steiner tree problem to within a poly-logarithmic factor. Currently there is a quasi-polynomial time algorithm that gives an <span class="math-container">$O(\log^3 k)$</span>-approximation. More precisely, one can obtain an <span class="math-container">$O(i^2 k^{1/i})$</span> approximation in <span class="math-container">$n^{O(i)}$</span> time. <a href="http://www.sciencedirect.com/science/article/pii/S0196677499910428" rel="nofollow noreferrer">http://www.sciencedirect.com/science/article/pii/S0196677499910428</a></p>
<p>Related to this problem is the Submodular Orienteering problem and its special cases. <a href="https://ieeexplore.ieee.org/document/1530718" rel="nofollow noreferrer">Link</a></p>

CC BY-SA 4.0
2015-11-17T05:07:41.447Z
2022-07-15T13:59:51.077Z
2022-07-15T13:59:51.077Z
Chandra Chekuri
<p>The following problem is known to have a quasi-polynomial time algorithm and it does not break any conjecture if in P. Given a hypergraph $\mathcal{H}:=(V,{\cal E}\subseteq 2^V)$, a transversal of ${\cal H}$ is a subset of $V$ that intersects every set in ${\cal E}$.</p>

<p><strong>Input.</strong> Two hypergraphs ${\cal H}$ and ${\cal T}$.</p>

<p><strong>Output.</strong> Either says that ${\cal T}$ is the set of (incluion-wise) minimal transversals of ${\cal H}$ or gives a counter-example.</p>

<p>The best known algorithm is a quasi-polynomial time algorithm (the first is the one by Fredman and Khachiyan  <a href="http://dx.doi.org/10.1006/jagm.1996.0062" rel="noreferrer">http://dx.doi.org/10.1006/jagm.1996.0062</a></p>

<p>The problem is  known as <em>Monotone Boolean Duality</em> or <em>Hypergraph Duality</em> and several enumeration problems are  reducible to this problem or equivalent to it (for instance the enumeration of minimal dominating sets is equivalent to this problem). It is actually believed to be in P.</p>

CC BY-SA 3.0
2015-11-18T08:51:01.517Z
2015-11-18T08:51:01.517Z
M. kanté
<p>What are some examples of problems with quasi-polynomial time ($QP$) algorithms that could conceivably be in $P$. In other words, they are in $QP$ for no obvious reason other than no one has found a polynomial-time algorithm?</p>

<p>This question is motivated by the recent graph isomorphism result (which is a valid answer to this question)</p>

<p>Some non-examples are</p>

<ul>
<li>Finding a clique of size $\log^{100} n$ in a graph </li>
<li>Finding a path of size $\log^{100} n$ in a graph </li>
<li>Solving k-sum for $k=\log^{100} n$</li>
<li>Minimum dominating set in a tournament </li>
</ul>

<p>Any of these problems being in $P$ would violate the exponential time hypothesis (ETH).</p>

CC BY-SA 3.0
2015-11-14T19:03:03.963Z
Graph Isomorphism for tournaments is known to be in quasi-polynomial time but it is not known to be in $P$. The existence of polynomial time algorithms would not violate any known complexity theoretic conjecture.
Mohammad Al-Turkistany
<polynomial-time>
Problems in quasi-polynomial time that could conceivably be in P (without causing collapses or violating widely held beliefs)
Anonanon
# Problems in quasi-polynomial time that could conceivably be in P (without causing collapses or violating widely held beliefs)

(Asked by: username_0 on 2015-11-14)

What are some examples of problems with quasi-polynomial time ($QP$) algorithms that could conceivably be in $P$. In other words, they are in $QP$ for no obvious reason other than no one has found a polynomial-time algorithm?

This question is motivated by the recent graph isomorphism result (which is a valid answer to this question)

Some non-examples are

* Finding a clique of size $\log^{100} n$ in a graph
* Finding a path of size $\log^{100} n$ in a graph
* Solving k-sum for $k=\log^{100} n$
* Minimum dominating set in a tournament

Any of these problems being in $P$ would violate the exponential time hypothesis (ETH).

**Tags:** polynomial-time
> **Comments:**
> **username_1**: Graph Isomorphism for tournaments is known to be in quasi-polynomial time but it is not known to be in $P$. The existence of polynomial time algorithms would not violate any known complexity theoretic conjecture.  

---

## 4 answers

### Answer by username_2 on 2015-11-17. Score: 13

Group Isomorphism! Although Ricky Demer gave lots (though certainly not all) details on this, there is an important point I want to highlight, esp. given the stated motivation for the question, namely:

> **Putting Group Isomorphism into $\mathsf{P}$ is a key obstacle to putting Graph Isomorphism into $\mathsf{P}$**

Group Isomorphism (when given by multiplication tables) reduces to Graph Isomorphism, so the above was technically always true. But when Graph Iso was way up at $2^{\tilde{O}(\sqrt{n})}$ it was so far from Group Iso's $2^{(\log n)^2}$ that there were clearly other obstacles in the way. If Graph Iso is in time $2^{(\log n)^{O(1)}}$, Group Isomorphism is then a much more immediately relevant obstacle to putting Graph Isomorphism into $\mathsf{P}$. In particular, this would suggest that Babai's algorithm handles much [1] of the combinatorics of GI, and the problem is now down to hard algebra. (Not that there's not hard algebra in GI, but GroupIso is *by definition* about algebra.)

[1] I won't say "all" of the combinatorics, because the exponent in Babai's algorithm is most likely $> 2$, which would still leave a gap between GI and GroupIso. Also because there may still be some combinatorics sitting inside the algebra of GroupIso...

> **Comments:**
> **username_1**: Nice. Your answer is perfectly suitable as an answer to this post: http://cstheory.stackexchange.com/questions/32160/what-evidence-is-there-that-graph-isomorphism-is-not-in-p  
> **username_2**: @MohammadAl-Turkistany: Only if you think that Group Iso isn't in P... Also, Thomas Kimpel's answer to that question already sort of hits on this point (but at the time, as I said, GI was so far from GroupIso that there could've in principle been other reasons for it not to be in P).  

---

### Answer by username_3 on 2015-11-17. Score: 12

Solving the [planted clique problem](https://en.wikipedia.org/wiki/Planted_clique) of distinguishing a uniformly random graph from the union of a random graph and a clique (of size intermediate between $2\log\_2 n$ and $\sqrt n$), with success probability bounded away from 1/2. It differs from your ETH-violating example of finding polylog-sized cliques in arbitrary graphs, because this is an average-case problem not a worst-case one.


---

### Answer by username_4 on 2015-11-17. Score: 8

Approximating the Directed Steiner tree problem to within a poly-logarithmic factor. Currently there is a quasi-polynomial time algorithm that gives an $O(\log^3 k)$-approximation. More precisely, one can obtain an $O(i^2 k^{1/i})$ approximation in $n^{O(i)}$ time. <http://www.sciencedirect.com/science/article/pii/S0196677499910428>

Related to this problem is the Submodular Orienteering problem and its special cases. [Link](https://ieeexplore.ieee.org/document/1530718)


---

### Answer by username_5 on 2015-11-18. Score: 6

The following problem is known to have a quasi-polynomial time algorithm and it does not break any conjecture if in P. Given a hypergraph $\mathcal{H}:=(V,{\cal E}\subseteq 2^V)$, a transversal of ${\cal H}$ is a subset of $V$ that intersects every set in ${\cal E}$.

**Input.** Two hypergraphs ${\cal H}$ and ${\cal T}$.

**Output.** Either says that ${\cal T}$ is the set of (incluion-wise) minimal transversals of ${\cal H}$ or gives a counter-example.

The best known algorithm is a quasi-polynomial time algorithm (the first is the one by Fredman and Khachiyan <http://dx.doi.org/10.1006/jagm.1996.0062>

The problem is known as *Monotone Boolean Duality* or *Hypergraph Duality* and several enumeration problems are reducible to this problem or equivalent to it (for instance the enumeration of minimal dominating sets is equivalent to this problem). It is actually believed to be in P.


---

