What is the fastest known algorithm(s) for finding a minimal sequence of tree rotations that transform given trees $A$ to $B$ (each with $n$ unlabeled nodes)? Equivalently, how can we find a shortest path between two elements in the Tamari lattice? Since Wikipedia lists the problem of finding the length of such a path as not known to be in polynomial time, presumably the best known algorithm is $O(c^n)$.
As a rough attempt at an upper bound, the Tamari lattice has $C_n$ nodes (Catalan's number), and by its definition each has degree $n-1$ (for the rotations of each of its internal nodes), while the diameter of the graph is at most $2n-2$, so an algorithm of Johnson 1982 for shortest paths yields an $O(C_nn\log\log n)$, or $4^{n-o(n)}$ upper bound.
(I would also be interested to know about polynomial time algorithms that find approximate solutions, for example with length $\le c\ell$ where $\ell$ is the shortest path.)