Problems in quasi-polynomial time that could conceivably be in P (without causing collapses or violating widely held beliefs)

Question

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

Answer 1

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

Answer 2

Solving the planted clique problem 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 3

Group isomorphism is another decently-known problem that's known
to be solvable in quasi-polynomial time. ​ That result can be generalized
to other finite objects which "extend" groups in a suitable sense -
[commutative semirings with the zero product property] and commutative groupoids
are both not close enough, but [Θ(1)-length tuples of groups with labels on some tuples
of sets of group elements (that are not necessarily from the same group)] all work.
(That is quite broad, since labeled tuples of singletons allow encoding functions,
and then having tuples of groups allows separate scalars and vectors.)

For this answer, groups are given by Cayley tables. ​ Bear in mind that the problems I'm going
to mention are only "really" known to be in SUBEXP when either [their underlying groups
are not necessarily all abelian] or [they can have "a large-enough amount" of labeling that is
not encompassed by [a "small" number of [[subgroups of direct sums of those groups] and/or
[functions from and to such subgroups which distribute over addition]]]], since otherwise
everything could be compressed exponentially by expressing things in terms of generating sets,
in which case giving the full tables instead would essentially amount to padding the input.

For inputs consisting of [an ordered pair $\langle \hspace{-0.02 in}$A,B$\hspace{-0.02 in}\rangle$ of such tuples tuples whose lengths are both L]
and [a non-negative integer c such that L and c are both in O(1)] and a length-L tuple of possible restrictions on injecitvity/surjectivity/zeroness, the existence of more than c [morphisms from
[the left object of that ordered pair] to [the right object of that ordered pair] for which the L
component group homomorphisms satisfy the corresponding restrictions] is decidable in
GC(O(log(max(cardinality_of_A's_groups))$\cdot$log(max(cardinality_of_B's_groups))),logspace)
by Reingold's result, since the verifier has two-way read access to the alleged proof.
Furthermore (still using Reingold), logspace machines can compute such morphisms given
2-way access to such witnesses, and if they additionally have 2-way access to a random tape,
then they can give [[a [proof-of-knowledge with respect to an extractor that has 2-way read access
to what it has already outputted] of a such a witness for isomorphism] with the same properties
as the usual ZKPoK for graph isomorphism] to a logspace verifier with 2-way read access to
its own randomness and the prover's messages. ​ Similarly, the HVSZK proof system for graph
non-isomorphism carries over essentially unchanged to objects of the type this paragraph is about.

Analogously to the previous paragraph, for non-negative integers k and objects
consisting of a group and a partial function from [the power-set of the group] to the group,
k-group-element sets are naturally represented with k$\cdot \hspace{-0.02 in}\lceil \hspace{-0.03 in}$log₂(cardinality_of_the_group)$\hspace{-0.02 in}\rceil$ bits
and "is a generating set" is checkable in logspace given 2-way read access to the set.

As a consequence, one gets gets that stuff ranging from the simple-to-state
"subgroup-isomorphism", to the moderate "minimum number of elements that can
be combined with a given subset of an abelian group to generate the whole group",
to the intentionally-complicated-to-state
"Given a domain whose scalars only need to form a ​ r$\hspace{.02 in}$ng ​ and a codomain with
not-necessarily-commutative "vector" addition, are there more then 3 algebra homomorphisms such that the map on scalars is not the zero ​ r$\hspace{.02 in}$ng ​ morphism and the map on "vectors" is injective?"
are all in GC$\hspace{-0.02 in}\big(\hspace{-0.03 in}O\big(\hspace{-0.03 in}$(log(n))$^2\hspace{-0.03 in}\big)\hspace{-0.03 in}$,logspace$\hspace{-0.03 in}\big)\hspace{-0.02 in}$, and thus in particular solvable in quasi-polynomial time.


Aside from the fact that [since 2011, significant work on the problem has "merely" halved the runtime's exponent for general groups and quartered the runtime's exponent for solvable groups],
I'm not aware of any evidence that such problems should not be in P.


Evidence that the problems this answer is about are "not so hard":

I already mentioned the ZKPoK and HVSZK proof system.
Whenever there are "not too many" non-isomorphic objects, [giving the verifier a "not to long" advice string and letting the proofs contain a pointer to locations in it] is enough to additionally
verify the complements of the type of problem this answer has been about before this sentence.
(The pointer is to where the advice string gives [2 reference objects
that the input objects are isomorphic to] and the answers for them.)
By this answer's bound on the number of non-isomorphic groups (which I don't know how to prove), whenever the labelled tuples are encompassed by the combination of
$\:\: \big[\hspace{-0.02 in}$O(1) bi-homomorphisms and O(log(n)) subgroups and
$\big[\hspace{-0.02 in}$other tuples such that the sum of their lengths is $O\big(\hspace{-0.03 in}$(log(n))$^2\hspace{-0.03 in}\big)\big]\big]\hspace{-0.02 in}$,
"not too long" will be "length $n^{O\left((\log(n))^{\hspace{.02 in}2}\hspace{-0.02 in}\right)}$". ​ ​ Also, this paper shows that
"the Group Non-Isomorphism problem" has "a 2-round Arthur-Merlin protocol" such that
"Arthur uses $O\big(\hspace{-0.03 in}$log⁶ n$\hspace{-0.03 in}\big)$ random bits and Merlin uses $O\big(\hspace{-0.03 in}$log² n$\hspace{-0.03 in}\big)$ non-deterministic bits"
and gives "a uniform NP machine for group non-isomorphism, that works
correctly on all but" quasi-polynomially many "inputs of any length".
Furthermore, that "NP machine is always correct when the input groups are non-isomorphic."

Answer 4

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

Answer 5

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.