What is the best terminology for lower bound The term lower bound comes from math and applies to more than just complexity theory. What we see is that such and such is "a" lower bound. In complexity theory should this not be phrased as "the" lower bound, or better still the lowest bound. I can see where lower is a relative term, but the complexity of a given problem would seem to have exactly one minimum. Am I being overly semantic here? what I would like to say is that the lower (or lowest) bound on the complexity of SLL(k) testing is exponential.

http://www.slkpg.com/NPcoNP.html
If you want to talk about the complexity of a problem, just use "the complexity of the problem" and don't bring lower bounds into it.

GOOD: "The complexity of SLL(k) testing is exponential."

GOOD: "The complexity of SLL(k) testing is at least exponential."

GOOD: "There is an exponential lower bound on the complexity of SLL(k) testing."

GOOD: "The complexity of SLL(k) testing is in $\Omega(2^n)$."

BAD: "The lower bound of SLL(k) is exponential."  &lt;--- Don't say this!  There's more than one valid lower bound.

BAD: ""The complexity is at least $O(2^n)$."  &lt;--- Don't say this!  Big-O is an upper bound; it doesn't go with "at least".