There are many places where the numbers $\pi$ and $(1+\sqrt5)/2$ show up. I'm curious to know about algorithms whose running time contains the golden ratio or $\pi$ in the exponent.
$\begingroup$
$\endgroup$
-
4$\begingroup$ Is there any particular computational reason to suspect that it might? And without knowing where it arises, do you think there's any particular insight to be gained if it does? $\endgroup$ – Niel de Beaudrap Jan 7 '13 at 18:25
-
13$\begingroup$ The golden ratio arises in the complexity analysis of programs that are similar in recursive structure to the recursion involved in the Fibonacci numbers: $F_{n+2} = F_{n+1} + F_n$. $\endgroup$ – Martin Berger Jan 7 '13 at 18:32
-
11$\begingroup$ The Fortnow and Melkebeek time/space lower-bound for SAT solvability contained the golden ratio ($n^{\phi - \epsilon}$ time and $n^{o(1)}$ space); but the exponent has been improved later by Ryan Williams. $\endgroup$ – Marzio De Biasi Jan 7 '13 at 19:51
-
2$\begingroup$ @MarzioDeBiasi I think your comment makes a good answer, even if the result was improved. The interesting thing is that there is an analysis that yields the golden ratio in the exponent $\endgroup$ – Sasho Nikolov Jan 8 '13 at 10:32
-
1$\begingroup$ @NieldeBeaudrap I hope to see some pattern among the examples. For example, the exponent e shows up in many places in randomized algorithms. I not surprised by that since I know that ball-and-bins kind of activity leads to answers which involve e. I was wondering if something like that can be said about algorithms that have golden ratio in the running times. $\endgroup$ – Plummer Jan 11 '13 at 12:12
$\begingroup$
$\endgroup$
It's the base rather than the exponent, but there's an $O(\varphi^k n^2)$ FPT time bound in
"An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization", Vida Dujmovic, Sue Whitesides, Algorithmica 40:15–31, 2004.
Also, it's a lower bound rather than an upper bound, but:
"An $n^{1.618}$ lower bound on the time to simulate one queue or two pushdown stores by one tape", Paul M.B. Vitányi, Inf. Proc. Lett. 21:147–152, 1985.
Finally, the one I was trying to find when I ran across those other two: the ham sandwich tree, a now-obsolete data structure in computational geometry for triangular range queries, has query time $O(n^{\log_2\varphi})\approx O(n^{0.695})$. So the golden ratio is properly in the exponent, but with a log rather than as itself. The data structure is a hierarchical partition of the plane into convex cells, with the overall structure of a binary tree, where each cell and its sibling in the tree are partitioned with a ham sandwich cut. The query time is determined by the recurrence $Q(n)=Q(\frac{n}{2})+Q(\frac{n}{4})+O(\log n)$, which has the above solution. It's described (with a more boring name) by
"Halfplanar range search in linear space and $O(n^{0.695})$ query time", Herbert Edelsbrunner, Emo Welzl, Inf. Proc. Lett. 23:289–293, 1986.
answered Jan 7 '13 at 22:02
-
1$\begingroup$ I’m not sure I would be comfortable with saying that $n^{\log_2\varphi}=\varphi^{\log_2n}$ has $\varphi$ in the exponent. $\endgroup$ – Emil Jeřábek Feb 1 '13 at 15:22
$\begingroup$
$\endgroup$
(from my comment above)
The Fortnow and Melkebeek time/space lower-bound for SAT solvability ($n^{\phi - \epsilon}$ time and $n^{o(1)}$ space) contained the golden ratio in the exponent; but it has been improved later by Ryan Williams.
answered Jan 8 '13 at 16:46
-
5$\begingroup$ While Ryan Williams spoiled your Fortnow and Melkebeek example, he also provided another one in the same field: in cs.cmu.edu/~ryanw/automated-lbs.pdf , he shows that there is no alternation-trading proof of $\mathrm{coNTIME}[n]\nsubseteq\mathrm{NTIMESPACE}[n^{\phi+o(1)},n^{o(1)}]$. $\endgroup$ – Emil Jeřábek Jan 14 '13 at 17:49
$\begingroup$
$\endgroup$
Also in the base rather than the exponent: the Monien-Speckenmeyer algorithm for 3-SAT has a running time of $\varphi^n\cdot O(n)$. That was the first non-trivial upper bound for 3-SAT.
answered Jan 8 '13 at 8:47
$\begingroup$
$\endgroup$
Another example of $\varphi$ in the base is an algorithm by Andreas Björklund and Thore Husfeldt to compute the parity of the number of directed Hamiltonian cycles, which runs in time $O(\varphi^n)$.
answered Jan 31 '13 at 15:13
$\begingroup$
$\endgroup$
Also in the base: The deletion–contraction algorithm (Zykov, 1949) for computing the number of graph colourings runs in time $O(\phi^{|E|+|V|})$. This is a very canonical example of how the golden ratio appears from a Fibonacci recurrence for the running time of evaluating a natural recursive formula; I’m sure it’s the oldest.
Mikko Koivisto found a $O(\phi^{|V|})$ algorithm for computing the number of perfect matchings (IWPEC 2009).
$\begingroup$
$\endgroup$
Golden ration in the base: A very recent FPT algorithm by Kociumaka and Pilipczuk, Faster deterministic Feedback Vertex Set computes a FVS of size $k$ in $O^*\left((2 + \phi)^k\right)$ time. (They then improves their algorithm to run in time $O^*(3.592^k)$.)
$\begingroup$
$\endgroup$
to expand on Martin Bergers comment: the ancient Euclidean GCD algorithm runs in worst case time on two successive elements from the Fibonacci sequence. more details on wikipedia which also states:
This proof, published by Gabriel Lamé in 1844, represents the beginning of computational complexity theory,[93] and also the first practical application of the Fibonacci numbers.[91]
technically the GCD algorithm runs in logarithmic time $O(\log(n))$ but the golden ratio shows up in the number of steps of the algorithm.
[1] what is the time complexity of Euclids algorithm, math.se
-
$\begingroup$ How is time and the number of steps different? $\endgroup$ – Nicholas Mancuso Jan 31 '13 at 20:53
-
$\begingroup$ sorry that should read # of arithmetic operations $\endgroup$ – vzn Jan 31 '13 at 22:56
-
1$\begingroup$ Lamé’s $\log_{\varphi}N$ bound is on the number of iterations of the main loop (or number of recursions, depending on the formulation of the algorithm). The running time of the algorithm is $O((\log N)^2)$ (that is, $O(n^2)$ in terms of the length of the input). $\endgroup$ – Emil Jeřábek Feb 1 '13 at 15:19
-
$\begingroup$ see the link. "let $T(a,b)$ be the number of steps taken in the Euclidean algorithm. $T(a,b)=O(log_\phi b)$" $\endgroup$ – vzn Feb 1 '13 at 15:49
-
1$\begingroup$ I don’t know which of the links you mean, but anyway I’m simply clarifying what is the meaning of “step” here so that it makes sense. Note also that writing $O(\log_\phi b)$ is pointless, as logarithms in any two bases are $O$ of each other. $\endgroup$ – Emil Jeřábek Feb 1 '13 at 19:01
