1

This definition from Wikipedia makes it simpler: Tight bounds An upper bound is said to be a tight upper bound, a least upper bound, or a supremum, if no smaller value is an upper bound. Similarly, a lower bound is said to be a tight lower bound, a greatest lower bound, or an infimum, if no greater value is a lower bound. https://en.wikipedia.org/wiki/...


1

The graph in question is a grid discretization of the phase space ($TC$ in the paper). Consider a 4-connected grid in the plane with 10x10 vertices. The branching factor of this graph is 4 (ignoring the boundary), but there are only 100 vertices in this graph total. BFS on this graph will not take exponential time because BFS throws away exponentially many ...


Only top voted, non community-wiki answers of a minimum length are eligible