The existence of short rotation sequences between any two trees implies that testing whether the rotation distance is at most belongs to the complexity class NP, but it is not known to be NP-complete, nor is it known to be solvable in polynomial time.