# Polynomial-time algorithms with huge exponent/constant

Do you know sensible algorithms that run in polynomial time in (Input length + Output length), but whose asymptotic running time in the same measure has a really huge exponent/constant (at least, where the proven upper bound on the running time is in such a way)?

-
See mathoverflow.net/questions/65412: "Worst known algorithm in terms of big-O or more precisely big-Theta." I posted an answer there. – Joseph O'Rourke May 19 '11 at 12:09
There's the Reingold's LOGSPACE algorithm for connectivity (see a question concerning it's time complexity), but doubt it's sensible in the sense you mean here... – Janne Korhonen May 19 '11 at 14:35
@Joseph ORourke: I have the "fat rectangle" paper on my desk right now! – Aaron Sterling May 19 '11 at 16:11
Although the $n^{42}$ was a legitimate calculation (dynamic programming pumps it up), I included it in the conference version as something of a joke, a joke removed in the journal version. – Joseph O'Rourke May 19 '11 at 17:13
Recognition of perfect graphs is in $O(|V(G)|^9)$, and a breakthrough seems to be necessary to improve this. – András Salamon May 23 '11 at 13:56

Algorithms based on the regularity lemma are good examples for polynomial-time algorithms with terrible constants (either in the exponent or as leading coefficients).

The regularity lemma of Szemeredi tells you that in any graph on $n$ vertices you can partition the vertices into sets where the edges between pairs of sets are "pseudo-random" (i.e., densities of sufficiently large subsets look like densities in a random graph). This is a structure that is very nice to work with, and as a consequence there are algorithms that use the partition. The catch is that the number of sets in the partition is an exponential tower in the parameter of pseudo-randomness (See here: http://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma).

For some links to algorithms that rely on the regularity lemma, see, e.g.: http://www.cs.cmu.edu/~ryanw/regularity-journ.pdf

-
Good point! Though, I'm not aware of a computational problem where there is a corresponding lower bound of tower of exponentials. Gowers proved such a lower bound for the regularity lemma itself, but I don't know of a computational problem where it applies. – arnab May 20 '11 at 17:50
I believe that the flocking algorithms described by Chazelle in this paper (arxiv.org/abs/0905.4241) have optimal (i.e have lower bounds) convergence that's a tower of twos – Suresh Venkat Jan 24 '12 at 22:39
In a recent paper (eccc.hpi-web.de/report/2014/018), I show some other algorithms using (arithmetic) regularity lemma that have huge constants hidden by O() notation. – arnab Jun 20 '14 at 7:21

Here are two screenshots from An Energy-Driven Approach to Linkage Unfolding by Jason H. Cantarella, Erik D. Demaine, Hayley N. Iben, James F. O’Brien, SOCG 2004:

-
The constant is way more impressive than the power of $n$ :) – Suresh Venkat May 27 '11 at 3:18
This is an algorithm with huge exponent AND huge constant... – Hsien-Chih Chang 張顯之 May 27 '11 at 3:18
The same bounds are true for Bubblesort. – Raphael Apr 3 '13 at 21:06
How tight are these bounds? – Max Apr 5 '14 at 15:45

News from SODA 2013: Max-Bisection problem is approximable to within a factor 0.8776 in around $O(n^{10^{100}})$ time.

-

Here is a recent result from FUN 2012 paper Picture-Hanging Puzzles by Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph S. B. Mitchell, Ronald L. Rivest and Mihai Patrascu.

We show how to hang a picture by wrapping rope around n nails, making a polynomial number of twists, such that the picture falls whenever any k out of the n nails get removed, and the picture remains hanging when fewer than k nails get removed.

Don't let the 'polynomial number' fool you...it turns out to be $O(n^{43737})$.

-
That's $(618)^{\text{#gates in an AKS sorting network}}$ (!!) – JɛﬀE Apr 11 '12 at 7:23

There exists a class of problems, whose solutions are hard to compute, but approximating them to any accuracy is easy, in the sense that there are polynomial-time algorithms that can approximate the solution to within $(1+\epsilon)$ for any constant ε > 0. However, there's a catch: the running time of the approximators may depend on $1/\epsilon$ quite badly, e.g., be $O(n^{1/\epsilon})$.

-

Although the run-time for such algorithms has been subsequently improved, the original algorithm for sampling a point from a convex body had run time $\tilde{O}(n^{19})$.

Dyer, Frieze, and Kannan: http://portal.acm.org/citation.cfm?id=102783

-

If $L$ is a tabular modal or superintuitionistic logic, then the extended Frege and substitution Frege proof systems for $L$ are polynomially equivalent, and polynomially faithfully interpretable in the classical EF (this is Theorem 5.10 in this paper of mine). The exponent $c$ of the polynomial simulations is not explicitly stated in Theorem 5.10, but the inductive proof of the theorem gives $c=2^{O(|F|)}$, where $F$ is a finite Kripke frame which generates $L$, so it can be as huge as you want depending on the logic. (It gets worse in Theorem 5.20.)

-

The current best known algorithm for recognizing map graphs (a generalization of planar graphs) runs in $n^{120}$. Thorup, Map graphs in polynomial time.

Computing the equilibrium of the Arrow-Debreu market takes $O(n^6\log(nU))$ max-flow computations, where $U$ is the maximum utility. Duan, Mehlhorn, A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market.

-
I get an error from IEEE when I follow your link, but I assume you're referring to Thorup's FOCS'98 paper "Map graphs in polynomial time". – David Eppstein Dec 7 '12 at 22:51
I do mean that paper, and it loads fine for me. – adrianN Dec 12 '12 at 19:45
works for me from the U. – Suresh Venkat Dec 12 '12 at 20:06

Sandpile Transience Problem

Consider the following process. Take a thick tile and drop sand particles on it one grain at a time. A heap gradually builds up and then a large portion of sand slides off from the edges of the tile. If we continue to add sand particles, after a certain point of time, the configuration of the heap repeats. Thereafter, the configuration becomes recurrent, i.e. it keeps revisiting a state that is seen earlier.

Consider the following model for the above process. Model the tile as an $n \times n$ grid. Sand particles are dropped on the vertices of this grid. If the number of particles at a vertex exceeds its degree, then the vertex collapses and the particles in it move to adjacent vertices (in cascading manner). A sand particle that reaches a boundary vertex disappears into a sink (`falls off'). This is known as the Abelian Sandpile Model.

Problem: How long does it take for the configuration to become recurrent in terms of $n$, assuming the worst algorithm for dropping sand particles?

In SODA '07, László Babai and Igor Gorodezky proved this time to be polynomially bounded but..

In SODA '12, Ayush Choure and Sundar Vishwanathan improved this bound to $O(n^7)$.

This answer would have looked slightly better if not for their improvement :)

-

The "convex skull" problem is to find the maximum-area convex polygon inside a given simple polygon. The fastest algorithm known for this problem runs in $O(n^7)$ time [Chang and Yap, DCG 1986].

-

The solution of Annihilation Games (Fraenkel and Yesha) has complexity $O(n^6)$.

-

There are some nonconstructive algorithms, most notably Fellows and Langston and Courcelle's theorem.

Also, Bodlaender's linear-time algorithm for tree-width and Courcelle's theorem are notoriously impractical.

-

The Robertson-Seymour theorem aka Graph Minor Theorem establishes among other things that for any graph $G$, there exists an $O(n^3)$ algorithm that determines whether an arbitrary graph $H$ (of size $n$) has $G$ as a minor. The proof is nonconstructive and the (I think non-uniform) multiplicative constant is probably so enormous that no formula for it can be written down explicitly (e.g. as a primitive recursive function on $G$).

http://en.wikipedia.org/wiki/Graph_minor_theorem#Polynomial_time_recognition

-

In their ICALP 2014 paper, Andreas Björklund and Thore Husfeldt give the first (randomized) polynomial algorithm that computes 2 disjoint paths with minimum total length (sum of the two paths length) between two given pairs of vertices. The running time is in $O(n^{11})$.

-

surprisingly one of the most obvious answers not posted yet. finding a clique of size $c$ (edges or vertices) apparently takes $O(n^c)$ time by the naive/brute force algorithm that enumerates all possibilities. or more accurately proportional to $n \choose c$ steps. (strangely enough this basic factoid seems to be rarely pointed out in the literature.) however a strict proof of that would imply $\mathsf{P \neq NP}$. so this question is related to the famous open conjecture, virtually equivalent to it. other NP type problems can be parameterized in this way.

-
1. there is a (simple) algorithm that improves the exponent slightly. 2. this is a much stronger statement than P not equal to NP, just as ETH is stronger than P not equal to NP. I think algorithms like this have not been pointed out because it seems that the OP is not interested in exhaustive search type of algorithms. – Sasho Nikolov Mar 14 '12 at 5:40
nitpicking: finding a clique with $c$ edges can be done in $n^{\sqrt{c}}$ or so time (since we are looking for a clique with $O(\sqrt{c})$ vertices). – Daniel Marx Mar 14 '12 at 8:41
you should be careful in conjecturing that all NP-complete problems are solvable only via brute force search. like I said, finding a clique can be sped up with matrix multiplication. for many other problems we have exact exponential time algorithms with better exponent than brute force search. what you're talking of most closely resembles the exponential time hypothesis: the (much stronger than P neq NP) conjecture that for all $k > 2$ $k$-SAT requires $2^{s_k n}$ time where $s_k > 0$. – Sasho Nikolov Mar 14 '12 at 16:04
There are many cases where brute force search is not optimal for an NP-hard problem. Three classic examples: (1) A vertex cover of size $k$ can be found in time e.g. $2^k\cdot n$, (2) A path of length $k$ can be found in a similar time, (3) A independent set of size $k$ in a planar graph can be found in time $2^{O(\sqrt{k})}\cdot n$. BTW: On the issue of ETH and the necessity of brute force, you might find our survey interesting: cs.bme.hu/~dmarx/papers/survey-eth-beatcs.pdf – Daniel Marx Mar 14 '12 at 20:36
@vzn: $2^{O(\sqrt{n})}$ is much faster than $2^{O(n)}$. – JɛﬀE Mar 14 '12 at 21:51

computing matrix rigidity[1] via brute force/naive/enumerations apparently takes $O(2^n)$ time for matrices of size $n$ elements. this can be seen as a converging limit of a sequence of increasingly accurate estimates that take $n \choose 1$, $n \choose 2$, $n \choose 3$, ... steps. in other words each estimate is in P-time $O(n^c)$ for any arbitrary exponent $c$ (ie $n \choose c$ steps). the naive algorithm chooses any $c$ elements of the matrix to change and tests for resulting dimension reduction. this is not totally surprising given that it has been related to computing circuit lower bounds. this follows a pattern where many algorithms have a conjectured P-time solution for some parameter but a solid proof of a lower bound would likely imply $\mathsf{P \neq NP}$ or something stronger.

-
Not sure how this is different (for example) from trying to find a max clique by enumerating over all sets of size k, for increasing k. each step is also p-time for fixed k. – Suresh Venkat Mar 14 '12 at 2:34
yes its very similar & reminds me of the Hartmanis isomorphism conjecture for NP sets. even if the isomorphism conjecture is not true (current consensus/conventional wisdom seems to lean against it), it seems NP sets have some similar property but maybe somewhat weaker, which also seems to require exhaustive search – vzn Mar 14 '12 at 15:09