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)?
Tell me more
×
Theoretical Computer Science Stack Exchange is a question and answer site for
theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
|
|
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 |
|||||||||
|
|
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:
|
|||||||||||||
|
![Corollary 2. The number of steps in our algorithm is at most $117607251220365312000 n^{79}(\ell_{\max}/d_{\min}(\Theta_0))^{26}$]](http://i.stack.imgur.com/YsEoD.png)
|
News from SODA 2013: Max-Bisection problem is approximable to within a factor 0.8776 in around $O(n^{10^{100}})$ time. |
||||
|
|
|
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})$. See more info here: http://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme. |
||||
|
|
|
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.
Don't let the 'polynomial number' fool you...it turns out to be $O(n^{43737})$. |
|||||
|
|
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.) |
||||
|
|
|
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 |
||||
|
|
|
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 solution of Annihilation Games (Fraenkel and Yesha) has complexity $O(n^6)$. |
||||
|
|
|
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 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. |
|||||||||
|
|
There are some nonconstructive algorithms, most notably Fellows and Langston and Courcelle's theorem. Also, Bodlaender's linear-time algorithm for tree-width is 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 |
||||
|
|
|
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. |
|||||||
|
|
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. |
|||||||||||||||||||||
|
