We all know P, or PTIME, I think, as a common name for the class of polynomial-time problems. Are there common names for the first few levels inside P; that is, for constant-time, linear-time, quadratic-time, cubic-time, ...? How do those names interact with common building blocks like "-SPACE" or "/poly"?
For linear-time algorithms, the Complexity Zoo gives LIN as a name, and extends that to NLIN by analogy with P and NP. In a drawing I made based on my reading of "Comparing Complexity Classes", I built the names "LINSPACE" and "NLINSPACE" according to what I think are community conventions.
If none exist, I have been imagining "KONST" for constant-time, "QUAD" for quadratic-time, and "CUB" (pronounced like "cub", "cube", or "kyubei", not sure) for cubic-time. I'm hoping that better community conventions already exist.
For examples of natural usage of these classes, I'd like to use the Chomsky hierarchy. Here, we have four extremely natural problems, and each corresponds to a level of complexity that has no nice name, but probably ought to:
- REG, the class of regular languages, is also DSPACE(1), or "KONSTSPACE" in my nonce terms.
- CFL $\subseteq$ DTIME($n^3$), or "CUB". This fact isn't in Complexity Zoo, which makes me feel a little strange; it's not a secret, is it? This class also closely relates to matrix multiplication, as CFL $\subseteq$ MM.
- CSL is also NSPACE(n), or "NLINSPACE".
- RE is fine as-is; we know quite a bit about RE.
In general, I see interesting things happening up to the third level of many hierarchies, and I think that even merely labeling up to the third level can be very useful.
I should divulge that I have a bias; I think mathematical objects should be nameable using only Unicode, and these clarified names clearly work towards that goal. Of course, "DTIME(n³)" is also still Unicode, but longer to spell, write, and say than "CUB".