What are notable examples of problems for which the best currently known algorithm has $2^{\Theta(n^2)}\text{poly}(n)$ running time ?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
New answer: The number of pseudo line arrangements is 2^{Theta(n^2)} http://page.math.tu-berlin.de/~felsner/Paper/numarr.pdf . Which is in turn can be used to bound the number order type of n points in the plane. Thus if you want to check some concrete conjecture on point configurations in the plane, you are going to get your desired running time. Examples of algorithms using this approach and use this approach are here: http://www.ist.tugraz.at/aichholzer/research/rp/triangulations/ordertypes/ . If you do not aggressively cut the search space for the specific conjecture you are checking, you would get the running you want.
In a similar direction, checking if a generic property holds for all binary n*n matrices, would take this running time. This in particular, the time it would take to verify a "generic" property over graphs over n vertices. As a "silly" example, think about a Ramsey type conjecture: Every graph over n vertices contains either a clique or an independent set of size $\Theta(\log n)$. Ha! This running time is explicitly mentioned in the Wikipedia page: http://en.wikipedia.org/wiki/Ramsey%27s_theorem#Ramsey_numbers.
Old answer: Some variants of Cylindrical algebraic decomposition if my memory serves me right.
http://en.wikipedia.org/wiki/Cylindrical_algebraic_decomposition
answered Jul 19, 2014 at 0:06
-
3$\begingroup$ The wiki page says that Collins algorithm is doubly exponential--that is, of the form $a^{b^n}$ for some $a$ and $b$. $\endgroup$ Commented Jul 19, 2014 at 3:51
-
$\begingroup$ It is lower for special cases... $\endgroup$ Commented Jul 20, 2014 at 4:46
-
$\begingroup$ Ok. I updated my answer... $\endgroup$ Commented Jul 20, 2014 at 16:12