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

<ul>
<li>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.</li>
<li>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. </li>
<li>There also is no natural reduction concept available on LIN, QUAD, CUB (except for reductions that are equally strong as the class itself). </li>
</ul>

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

CC BY-SA 4.0
2019-10-21T21:16:53.570Z
I disagree with bullet point (3) -- why not use linear time reductions (in whatever the fixed model is)? I also partially disagree with bullet point (1) -- I don't think that "not robust" is the same as "artificial."
Huck Bennett
CC BY-SA 4.0
2019-10-21T22:17:19.413Z
On one hand, I grok Fortnow's reasoning in https://cstheory.stackexchange.com/a/3448/52212 that if we start with LIN and ask for self-lowness then we get P. However, there is still another "pre-categorical" composition property in LIN: we can concatenate two programs in LIN together and get another one still in LIN.
Corbin
CC BY-SA 4.0
2019-11-02T00:49:26.640Z
Accepted. One final note: In descriptive complexity, P is very natural but none of its subtiers are. I wonder whether any connection exists to *linear logic* in such a way; probably not, and a cursory search turned up nothing neither.
Corbin
CC BY-SA 4.0
2021-02-20T15:38:43.367Z
Sorry to post a zombie comment, but somehow I missed https://golem.ph.utexas.edu/category/2019/11/total_maps_of_turing_categorie.html which notes the same thing I did, but more rigorously: LIN can be made to work as a total maps category.
Corbin
CC BY-SA 4.0
2019-10-21T18:28:14.240Z
2019-10-21T18:28:14.240Z
Gamow
<p>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"?</p>

<p>For linear-time algorithms, the Complexity Zoo gives <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:L#lin" rel="nofollow noreferrer">LIN</a> as a name, and extends that to <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#nlin" rel="nofollow noreferrer">NLIN</a> by analogy with P and NP. In <a href="https://github.com/MostAwesomeDude/zaha/blob/master/complexity/decision/comparing-complexity-classes.png" rel="nofollow noreferrer">a drawing I made</a> based on my reading of <a href="https://doi.org/10.1016/S0022-0000(74)80008-5" rel="nofollow noreferrer">"Comparing Complexity Classes"</a>, I built the names "LINSPACE" and "NLINSPACE" according to what I think are community conventions.</p>

<p>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.</p>

<p>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:</p>

<ul>
<li>REG, the class of regular languages, is also DSPACE(1), or "KONSTSPACE" in my nonce terms.</li>
<li>CFL <span class="math-container">$\subseteq$</span> DTIME(<span class="math-container">$n^3$</span>), 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 <span class="math-container">$\subseteq$</span> MM.</li>
<li>CSL is also NSPACE(n), or "NLINSPACE".</li>
<li>RE is fine as-is; we know quite a bit about RE.</li>
</ul>

<p>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.</p>

<p>I should divulge that I have a bias; <a href="https://twitter.com/corbinsimpson/status/1162509205808353280" rel="nofollow noreferrer">I think mathematical objects should be nameable using only Unicode</a>, 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".</p>

<cc.complexity-theory><complexity-classes><time-complexity>
Are there common names for the subtiers of PTIME?
Corbin
# Are there common names for the subtiers of PTIME?

(Asked by: username_0 on 2019-10-21)

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](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:L#lin) as a name, and extends that to [NLIN](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#nlin) by analogy with P and NP. In [a drawing I made](https://github.com/MostAwesomeDude/zaha/blob/master/complexity/decision/comparing-complexity-classes.png) based on my reading of ["Comparing Complexity Classes"](https://doi.org/10.1016/S0022-0000(74)80008-5), 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](https://twitter.com/corbinsimpson/status/1162509205808353280), 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".

**Tags:** cc.complexity-theory, complexity-classes, time-complexity


---

## 1 answers

### Answer by username_1 on 2019-10-21. Score: 7 | Accepted answer

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.

> **Comments:**
> **username_2**: I disagree with bullet point (3) -- why not use linear time reductions (in whatever the fixed model is)? I also partially disagree with bullet point (1) -- I don't think that "not robust" is the same as "artificial."  
> **username_0**: On one hand, I grok Fortnow's reasoning in https://cstheory.stackexchange.com/a/3448/52212 that if we start with LIN and ask for self-lowness then we get P. However, there is still another "pre-categorical" composition property in LIN: we can concatenate two programs in LIN together and get another one still in LIN.  
> **username_0**: Accepted. One final note: In descriptive complexity, P is very natural but none of its subtiers are. I wonder whether any connection exists to *linear logic* in such a way; probably not, and a cursory search turned up nothing neither.  
> **username_0**: Sorry to post a zombie comment, but somehow I missed https://golem.ph.utexas.edu/category/2019/11/total_maps_of_turing_categorie.html which notes the same thing I did, but more rigorously: LIN can be made to work as a total maps category.  

---

