<p>News from <a href="http://arxiv.org/pdf/1205.0458v2.pdf">SODA 2013</a>: Max-Bisection problem is approximable to within a factor 0.8776 in around $O(n^{10^{100}})$ time.</p>

CC BY-SA 3.0
2012-09-22T09:42:55.053Z
2012-09-22T09:42:55.053Z
Jagadish
<p>Here are two screenshots from <a href="http://graphics.eecs.berkeley.edu/papers/Cantarella-AED-2004-06/" rel="noreferrer">An Energy-Driven Approach to Linkage Unfolding</a> by Jason H. Cantarella, Erik D. Demaine, Hayley N. Iben,  James F. O’Brien, SOCG 2004:</p>

<p><img src="https://i.sstatic.net/Q2BCV.png" alt="Corollary 1. The number of steps in our algorithm is at most $1752484608000 n^{79}L^{25}/D^{26}(\Theta_0)$"></p>

<p><img src="https://i.sstatic.net/YsEoD.png" alt="Corollary 2. The number of steps in our algorithm is at most $117607251220365312000 n^{79}(\ell_{\max}/d_{\min}(\Theta_0))^{26}$]"></p>

CC BY-SA 3.0
2011-05-27T03:18:30.693Z
The constant is way more impressive than the power of $n$ :)
Suresh Venkat
CC BY-SA 3.0
2011-05-27T03:18:37.727Z
This is an algorithm with huge exponent AND huge constant...
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2013-04-03T21:06:52.863Z
The same bounds are true for Bubblesort.
Raphael
CC BY-SA 3.0
2014-04-05T15:45:08.857Z
How tight are these bounds?
Max
CC BY-SA 3.0
2011-05-27T03:03:22.960Z
2011-05-27T03:03:22.960Z
Jeffε
<p>Here is a recent result from FUN 2012 paper <a href="http://arxiv.org/abs/1203.3602">Picture-Hanging Puzzles</a> by Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph S. B. Mitchell, Ronald L. Rivest and Mihai Patrascu.</p>

<blockquote>
  <p>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.</p>
</blockquote>

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

CC BY-SA 3.0
2012-04-11T07:23:12.630Z
That's $(618)^{\text{#gates in an AKS sorting network}}$ (!!)
Jeffε
CC BY-SA 3.0
2012-04-11T05:29:22.727Z
2012-04-11T05:29:22.727Z
Jagadish
<p>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})$. </p>

<p>Dyer, Frieze, and Kannan: <a href="http://portal.acm.org/citation.cfm?id=102783">http://portal.acm.org/citation.cfm?id=102783</a></p>

CC BY-SA 3.0
2011-05-23T11:51:23.187Z
2011-05-23T11:51:23.187Z
Aaron Roth
<p>The current best known algorithm for recognizing map graphs (a generalization of planar graphs) runs in <span class="math-container">$n^{120}$</span>. <a href="http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=743490" rel="nofollow noreferrer">Thorup, Map graphs in polynomial time.</a></p>
<p>Computing the equilibrium of the Arrow-Debreu market takes <span class="math-container">$O(n^6\log(nU))$</span> max-flow computations, where <span class="math-container">$U$</span> is the maximum utility. <a href="http://arxiv.org/abs/1212.0979" rel="nofollow noreferrer">Duan, Mehlhorn, A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market.</a></p>

CC BY-SA 3.0
2012-12-07T22:51:28.627Z
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
CC BY-SA 3.0
2012-12-12T19:45:03.647Z
I do mean that paper, and it loads fine for me.
adrianN
CC BY-SA 3.0
2012-12-12T20:06:17.207Z
works for me from the U.
Suresh Venkat
CC BY-SA 4.0
2012-12-07T09:15:02.777Z
2022-07-13T23:11:47.993Z
2022-07-13T23:11:47.993Z
adrianN
<p>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 <a href="http://math.cas.cz/~jerabek/papers/sfef.pdf">this paper</a> 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.)</p>

CC BY-SA 3.0
2012-01-24T15:19:06.390Z
2012-01-24T16:02:23.823Z
2012-01-24T16:02:23.823Z
Emil Jeřábek
<p>There exists a class of problems, whose solutions are hard to compute, but approximating them to any accuracy is <em>easy</em>, 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})$.</p>

<p>See more info here: <a href="http://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme">http://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme</a>.</p>

CC BY-SA 3.0
2011-05-19T15:54:54.533Z
2011-05-25T19:39:02.330Z
2011-05-25T19:39:02.330Z
Sadeq Dousti
<p>The solution of <a href="http://www.sciencedirect.com/science/article/pii/0095895682900582">Annihilation Games</a> (Fraenkel and Yesha) has complexity $O(n^6)$.</p>

CC BY-SA 3.0
2011-05-23T04:53:36.223Z
2011-05-23T04:53:36.223Z
Yuval Filmus
<p>There are some nonconstructive algorithms, most notably <a href="http://dx.doi.org/10.1145/44483.44491" rel="noreferrer">Fellows and Langston</a><strike> and <a href="http://dx.doi.org/10.1016/0890-5401%2890%2990043-H" rel="noreferrer">Courcelle's theorem</a></strike>.</p>

<p>Also, <a href="http://dx.doi.org/10.1137/S0097539793251219" rel="noreferrer">Bodlaender's linear-time algorithm</a> for tree-width  and <a href="http://dx.doi.org/10.1016/0890-5401%2890%2990043-H" rel="noreferrer">Courcelle's theorem</a> are notoriously impractical.</p>

CC BY-SA 3.0
2012-12-06T17:25:46.710Z
2014-06-20T02:49:25.923Z
2014-06-20T02:49:25.923Z
Yixin Cao
<p>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$).</p>

<p><a href="http://en.wikipedia.org/wiki/Graph_minor_theorem#Polynomial_time_recognition">http://en.wikipedia.org/wiki/Graph_minor_theorem#Polynomial_time_recognition</a></p>

CC BY-SA 3.0
2012-12-12T19:03:32.557Z
2012-12-12T19:03:32.557Z
none
<p>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, <em>DCG</em> 1986].</p>

CC BY-SA 3.0
2011-05-27T03:43:14.157Z
2011-05-27T03:43:14.157Z
Jeffε
<p><strong>Sandpile Transience Problem</strong></p>

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

<p>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 <strong>Abelian Sandpile Model</strong>.</p>

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

<p>In <a href="http://people.cs.uchicago.edu/~laci/papers/bg-sandpile-soda07.pdf" rel="noreferrer">SODA '07</a>, László Babai and Igor Gorodezky proved this time to be polynomially bounded but..</p>

<p><img src="https://i.sstatic.net/VRm3y.jpg" alt="enter image description here"></p>

<p>In <a href="http://arxiv.org/abs/1105.3368" rel="noreferrer">SODA '12</a>, Ayush Choure and Sundar Vishwanathan improved this bound to $O(n^7)$.</p>

<p>This answer would have looked slightly better if not for their improvement :)</p>

CC BY-SA 3.0
2012-03-14T14:45:04.483Z
2012-03-14T15:28:05.503Z
2012-03-14T15:28:05.503Z
Jagadish
<p>In their <a href="http://thorehusfeldt.files.wordpress.com/2010/08/spdp-e5d5661.pdf" rel="noreferrer">ICALP 2014</a> 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})$.</p>

CC BY-SA 3.0
2015-10-02T09:53:47.453Z
2015-10-02T15:46:39.960Z
2015-10-02T15:46:39.960Z
Lamine
<p>In <a href="https://nanoexplanations.wordpress.com/2011/12/09/polygon-rectangulation-part-2-minimum-number-of-fat-rectangles/" rel="noreferrer">Polygon rectangulation, part 2: Minimum number of fat rectangles</a>, a practical modification of the rectangle partition problem motivated by concerns in VLSI is presented:</p>

<blockquote>
  <p>Fat Rectangle Optimization Problem: Given an orthogonal polygon $P$, maximize the shortest side $\delta$ over all rectangulations of $P$.  Among the partitions with the same $\delta$, choose the partition with the fewest number of rectangles.</p>
</blockquote>

<p>As yet, only a theoretical algorithm exists, with a running time of $O(n^{42})$. (That is not a typo, and it is obtained through a “natural” dynamic programming solution to the problem stated there.)</p>

CC BY-SA 3.0
2018-01-22T00:44:16.977Z
2018-01-22T00:44:16.977Z
Thomas Klimpel
<p>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.</p>

CC BY-SA 3.0
2012-03-14T05:40:06.413Z
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
CC BY-SA 3.0
2012-03-14T08:41:11.620Z
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
CC BY-SA 3.0
2012-03-14T15:12:22.263Z
SN-- OP says nothing about excluding "exhaustive search type of algorithms" which opens the field substantially because many NP problems are like this for a given parameter like above example for clique finding, in fact it may be a somewhat general property. in fact a proof that P!=NP might be basically equivalent to showing that _all_ NP problems are only solvable via brute force methods. ps analogous formulation for SAT might be, "c of the variables are true and remaining are false" etc.
vzn
CC BY-SA 3.0
2012-03-14T16:01:03.230Z
i take "sensible" to exclude this kind of examples. also the running time of exhaustive enumeration says nothing about algorithmic techniques, it's just a statement about output range size.
Sasho Nikolov
CC BY-SA 3.0
2012-03-14T16:04:05.020Z
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
CC BY-SA 3.0
2012-03-14T20:36:03.563Z
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: http://www.cs.bme.hu/~dmarx/papers/survey-eth-beatcs.pdf
Daniel Marx
CC BY-SA 3.0
2012-03-14T20:37:24.060Z
conjecture that NP requires some form of brute force search seems reasonable to me & related to, maybe at heart of P=?NP; dont think the matrix-multiplication-based clique finding algorithm is evidence otherwise. NP seems to require brute force search of "something"; what that "something" is, is not yet clear. there are faster algorithms than brute force but not "much faster" & one could reasonably conjecture that they are also roughly equivalent to a brute force search of "something". agree ETH is also highly relevant
vzn
CC BY-SA 3.0
2012-03-14T21:51:18.447Z
@vzn: $2^{O(\sqrt{n})}$ is **much** faster than $2^{O(n)}$.
Jeffε
CC BY-SA 3.0
2012-03-13T22:31:01.610Z
2012-03-13T22:31:01.610Z
vzn
<p>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.</p>

<p>[1] <a href="https://cstheory.stackexchange.com/questions/10581/questions-about-computing-matrix-rigidity">Questions about computing matrix rigidity</a></p>

CC BY-SA 3.0
2012-03-14T02:34:28.657Z
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
CC BY-SA 3.0
2012-03-14T15:09:36.400Z
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
CC BY-SA 3.0
2012-03-13T23:03:30.163Z
2012-03-13T23:03:30.163Z
2017-04-13T12:32:28.117Z
vzn
<p>Algorithms based on the regularity lemma are good examples for polynomial-time algorithms with terrible constants (either in the exponent or as leading coefficients).</p>

<p>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: <a href="http://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma">http://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma</a>).</p>

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

CC BY-SA 3.0
2011-05-20T17:50:20.520Z
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
CC BY-SA 3.0
2012-01-24T22:39:46.313Z
I believe that the flocking algorithms described by Chazelle in this paper (http://arxiv.org/abs/0905.4241) have optimal (i.e have lower bounds) convergence that's a tower of twos
Suresh Venkat
CC BY-SA 3.0
2014-06-20T07:21:16.530Z
In a recent paper (http://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
CC BY-SA 3.0
2011-05-19T15:33:52.000Z
2011-05-19T15:33:52.000Z
Dana Moshkovitz
<p>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 <em>huge</em> exponent/constant (at least, where the proven upper bound on the running time is in such a way)?</p>

CC BY-SA 3.0
2011-05-19T12:09:15.923Z
See http://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
CC BY-SA 3.0
2011-05-19T14:35:46.427Z
There's the Reingold's LOGSPACE algorithm for connectivity (see [a question concerning it's time complexity](http://cstheory.stackexchange.com/questions/1063/time-complexity-analysis-for-reingolds-ust-conn-algorithm)), but doubt it's sensible in the sense you mean here...
Janne H. Korhonen
CC BY-SA 3.0
2011-05-19T15:17:47.823Z
@Joseph O'Rourke: Corrected that one, thanks! Your O(n^42) algorithm is precisely what I am looking for, and the paper is [here](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.111.7034), if anyone is interested (I would have written this as an answer, but my karma forbids me this at this time).
Joris
CC BY-SA 3.0
2011-05-19T15:24:34.013Z
@Janne Korhonen: That is near to what I am looking for (not exactly because the problem is trivial for polynomial space). I wrote "sensible" because I would otherwise have expected comments of the form "You always can loop for n^BB(42) steps after you have finished".
Joris
CC BY-SA 3.0
2011-05-19T16:11:17.777Z
@Joseph ORourke: I have the "fat rectangle" paper on my desk right now!
Aaron Sterling
CC BY-SA 3.0
2011-05-19T17:13:38.520Z
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](http://en.wikipedia.org/wiki/42_%28number%29), a joke removed in the journal version.
Joseph O'Rourke
CC BY-SA 3.0
2011-05-23T13:56:54.583Z
Recognition of perfect graphs is in $O(|V(G)|^9)$, and a breakthrough seems to be necessary to improve this.
András Salamon
<ds.algorithms><big-list>
Polynomial-time algorithms with huge exponent/constant
Joris
# Polynomial-time algorithms with huge exponent/constant

(Asked by: username_0 on 2011-05-19)

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

**Tags:** ds.algorithms, big-list

> **Comments:**
> **username_1**: See http://mathoverflow.net/questions/65412/: "Worst known algorithm in terms of big-O or more precisely big-Theta." I posted an answer there.  
> **username_2**: There's the Reingold's LOGSPACE algorithm for connectivity (see [a question concerning it's time complexity](http://cstheory.stackexchange.com/questions/1063/time-complexity-analysis-for-reingolds-ust-conn-algorithm)), but doubt it's sensible in the sense you mean here...  
> **username_0**: @username_1: Corrected that one, thanks! Your O(n^42) algorithm is precisely what I am looking for, and the paper is [here](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.111.7034), if anyone is interested (I would have written this as an answer, but my karma forbids me this at this time).  
> **username_0**: @Janne Korhonen: That is near to what I am looking for (not exactly because the problem is trivial for polynomial space). I wrote "sensible" because I would otherwise have expected comments of the form "You always can loop for n^BB(42) steps after you have finished".  
> **username_3**: @Joseph ORourke: I have the "fat rectangle" paper on my desk right now!  
> **username_1**: 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](http://en.wikipedia.org/wiki/42_%28number%29), a joke removed in the journal version.  
> **username_4**: Recognition of perfect graphs is in $O(|V(G)|^9)$, and a breakthrough seems to be necessary to improve this.  

---

## 17 answers

### Answer by username_24 on 2011-05-19. Score: 45 | Accepted answer

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>

> **Comments:**
> **username_25**: 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.  
> **username_7**: I believe that the flocking algorithms described by Chazelle in this paper (http://arxiv.org/abs/0905.4241) have optimal (i.e have lower bounds) convergence that's a tower of twos  
> **username_25**: In a recent paper (http://eccc.hpi-web.de/report/2014/018/), I show some other algorithms using (arithmetic) regularity lemma that have huge constants hidden by O() notation.  

---

### Answer by username_5 on 2012-09-22. Score: 60

News from [SODA 2013](http://arxiv.org/pdf/1205.0458v2.pdf): username_10-Bisection problem is approximable to within a factor 0.8776 in around $O(n^{10^{100}})$ time.


---

### Answer by username_6 on 2011-05-27. Score: 60

Here are two screenshots from [An Energy-Driven Approach to Linkage Unfolding](http://graphics.eecs.berkeley.edu/papers/Cantarella-AED-2004-06/) by Jason H. Cantarella, Erik D. Demaine, Hayley N. Iben, James F. O’Brien, SOCG 2004:

![Corollary 1. The number of steps in our algorithm is at most $1752484608000 n^{79}L^{25}/D^{26}(\Theta_0)$](https://i.sstatic.net/Q2BCV.png)

![Corollary 2. The number of steps in our algorithm is at most $117607251220365312000 n^{79}(\ell_{\max}/d_{\min}(\Theta_0))^{26}$]](https://i.sstatic.net/YsEoD.png)

> **Comments:**
> **username_7**: The constant is way more impressive than the power of $n$ :)  
> **username_8**: This is an algorithm with huge exponent AND huge constant...  
> **username_9**: The same bounds are true for Bubblesort.  
> **username_10**: How tight are these bounds?  

---

### Answer by username_5 on 2012-04-11. Score: 40

Here is a recent result from FUN 2012 paper [Picture-Hanging Puzzles](http://arxiv.org/abs/1203.3602) 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})$.

> **Comments:**
> **username_6**: That's $(618)^{\text{#gates in an AKS sorting network}}$ (!!)  

---

### Answer by username_15 on 2011-05-19. Score: 27

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


---

### Answer by username_11 on 2011-05-23. Score: 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>


---

### Answer by username_12 on 2012-12-07. Score: 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.](http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=743490)

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.](http://arxiv.org/abs/1212.0979)

> **Comments:**
> **username_13**: 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".  
> **username_12**: I do mean that paper, and it loads fine for me.  
> **username_7**: works for me from the U.  

---

### Answer by username_14 on 2012-01-24. Score: 20

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](http://math.cas.cz/~jerabek/papers/sfef.pdf) 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.)


---

### Answer by username_6 on 2011-05-27. Score: 15

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


---

### Answer by username_5 on 2012-03-14. Score: 15

**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](http://people.cs.uchicago.edu/~laci/papers/bg-sandpile-soda07.pdf), László Babai and Igor Gorodezky proved this time to be polynomially bounded but..

![enter image description here](https://i.sstatic.net/VRm3y.jpg)

In [SODA '12](http://arxiv.org/abs/1105.3368), Ayush Choure and Sundar Vishwanathan improved this bound to $O(n^7)$.

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


---

### Answer by username_16 on 2011-05-23. Score: 14

The solution of [Annihilation Games](http://www.sciencedirect.com/science/article/pii/0095895682900582) (Fraenkel and Yesha) has complexity $O(n^6)$.


---

### Answer by username_17 on 2012-12-06. Score: 13

There are some nonconstructive algorithms, most notably [Fellows and Langston](http://dx.doi.org/10.1145/44483.44491) and [Courcelle's theorem](http://dx.doi.org/10.1016/0890-5401%2890%2990043-H).

Also, [Bodlaender's linear-time algorithm](http://dx.doi.org/10.1137/S0097539793251219) for tree-width and [Courcelle's theorem](http://dx.doi.org/10.1016/0890-5401%2890%2990043-H) are notoriously impractical.


---

### Answer by username_18 on 2012-12-12. Score: 12

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>


---

### Answer by username_19 on 2015-10-02. Score: 10

In their [ICALP 2014](http://thorehusfeldt.files.wordpress.com/2010/08/spdp-e5d5661.pdf) 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})$.


---

### Answer by username_20 on 2018-01-22. Score: 5

In [Polygon rectangulation, part 2: Minimum number of fat rectangles](https://nanoexplanations.wordpress.com/2011/12/09/polygon-rectangulation-part-2-minimum-number-of-fat-rectangles/), a practical modification of the rectangle partition problem motivated by concerns in VLSI is presented:

> Fat Rectangle Optimization Problem: Given an orthogonal polygon $P$, maximize the shortest side $\delta$ over all rectangulations of $P$. Among the partitions with the same $\delta$, choose the partition with the fewest number of rectangles.

As yet, only a theoretical algorithm exists, with a running time of $O(n^{42})$. (That is not a typo, and it is obtained through a “natural” dynamic programming solution to the problem stated there.)


---

### Answer by username_21 on 2012-03-13. Score: -2

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.

> **Comments:**
> **username_22**: 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.  
> **username_23**: 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).  
> **username_21**: SN-- OP says nothing about excluding "exhaustive search type of algorithms" which opens the field substantially because many NP problems are like this for a given parameter like above example for clique finding, in fact it may be a somewhat general property. in fact a proof that P!=NP might be basically equivalent to showing that _all_ NP problems are only solvable via brute force methods. ps analogous formulation for SAT might be, "c of the variables are true and remaining are false" etc.  
> **username_22**: i take "sensible" to exclude this kind of examples. also the running time of exhaustive enumeration says nothing about algorithmic techniques, it's just a statement about output range size.  
> **username_22**: 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$.  
> **username_23**: 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: http://www.cs.bme.hu/~dmarx/papers/survey-eth-beatcs.pdf  
> **username_21**: conjecture that NP requires some form of brute force search seems reasonable to me & related to, maybe at heart of P=?NP; dont think the matrix-multiplication-based clique finding algorithm is evidence otherwise. NP seems to require brute force search of "something"; what that "something" is, is not yet clear. there are faster algorithms than brute force but not "much faster" & one could reasonably conjecture that they are also roughly equivalent to a brute force search of "something". agree ETH is also highly relevant  
> **username_6**: @username_21: $2^{O(\sqrt{n})}$ is **much** faster than $2^{O(n)}$.  

---

### Answer by username_21 on 2012-03-13. Score: -2

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.

[1] [Questions about computing matrix rigidity](https://cstheory.stackexchange.com/questions/10581/questions-about-computing-matrix-rigidity)

> **Comments:**
> **username_7**: 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.  
> **username_21**: 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  

---

