Before revision:  As far as we know, this is the first natural problem with a quasi-polynomial lower bound that is shown to be tight .
After revision:  This shows that the hyperbolic plane is a potential source of NP-intermediate problems .