1
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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." $\endgroup$ – Huck Bennett Oct 21 at 21:16
  • 1
    $\begingroup$ On one hand, I grok Fortnow's reasoning in 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. $\endgroup$ – Corbin Oct 21 at 22:17
  • $\begingroup$ 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. $\endgroup$ – Corbin Nov 2 at 0:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.