8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mohammad Al-Turkistany Nov 14 '15 at 19:03
12
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Nice. Your answer is perfectly suitable as an answer to this post: cstheory.stackexchange.com/questions/32160/… $\endgroup$ – Mohammad Al-Turkistany Nov 17 '15 at 7:09
  • $\begingroup$ @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). $\endgroup$ – Joshua Grochow Nov 17 '15 at 16:09
10
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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}$log2(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}$log6 n$\hspace{-0.03 in}\big)$ random bits and Merlin uses $O\big(\hspace{-0.03 in}$log2 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."

$\endgroup$
  • $\begingroup$ factoring, discrete log? $\endgroup$ – user34945 Nov 14 '15 at 21:59
  • $\begingroup$ Those are not known to be solvable by in quasi-polynomial time by classical computers. $\;$ $\endgroup$ – user6973 Nov 14 '15 at 22:05
  • $\begingroup$ @Arul: Factoring reduces to ring iso, when the rings are given by generators and relations. Not when they are given by their full multiplication tables (in the latter case Ring Iso, like Group Iso, has a quasi-poly-time algorithm). $\endgroup$ – Joshua Grochow Nov 17 '15 at 0:49
  • 1
    $\begingroup$ @JoshuaGrochow ' Factoring reduces to ring iso, when the rings are given by generators and relations' could you share the reduction or reference? $\endgroup$ – user34945 Nov 17 '15 at 4:35
  • 1
    $\begingroup$ @Arul: Actually, something stronger than what I wrote before is true. Factoring reduces to ring iso even when the ring is given by a linear basis and structure coefficients (see Sec. 2 of Kayal-Saxena for what that means). Table model means the input literally lists out all the elements of the ring (which can be done if the ring is finite), and for each pair says what their sum is and what their product is. $\endgroup$ – Joshua Grochow Nov 17 '15 at 16:20
7
$\begingroup$

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. http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=1530718&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D1530718

$\endgroup$
5
$\begingroup$

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.

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