questions about lowerbounds on functions, usually the complexity of an algorithm or a problem
This tag is mainly used for questions related to lowerbounds on the amount of computational recourses (like time, space, circuit size, circuit depth, etc.) used by an algorithm or required to solve a problem.
Typically a lowerbound is a result showing that a problem cannot be computed by certain amount of resources, and demonstrates the difficulty of solving the problem.
A hardness result (a.k.a universality) should not be confused with a lowerbound result. Hardness of a problem for a class means that a problem is as difficult as any other problem in that class, whereas a lowerbound for a problem shows that the problem is outside that class. For hardness results please use hardness.
This tag is often combined with cc.complexity-theory or co.combinatorics.
