Are there common names for the subtiers of PTIME?

Question

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".

Answer 1

As complexity classes LIN, QUAD, CUB etc are not well-behaved, and not easy to handle.

• In the definition, you must freeze the model of computation (that is, deterministic Turing machines with one tape). So you will do complexity theory in a single artificial model.
• The definition of these classes is fragile: In contrast to our standard complexity classes, the classes LIN, QUAD, CUB do not remain stable if you move to other models, like RAMs or Turing machine with two tapes.
• There also is no natural reduction concept available on LIN, QUAD, CUB (except for reductions that are equally strong as the class itself).

Summary: All in all this means trouble, and the classes are not very appealing.