What is the best terminology for lower bound
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".