# Are there problems that are DSPACE(O(1)) complete?

I know there are problems that are NL-complete, NP-Complete, PSPACE-complete, etc. Are there problems that are DSPACE(O(1))-complete I.e. NSPACE(O(1))-Complete I.e. Reg-Complete?

Thanks!

• Complete with respect to what kind of reduction? – Yuval Filmus Oct 4 '18 at 3:59
• @Yuval Filmus, this is a great point I hadn't thought of. I'm not well versed with L vs. NL but are NL-complete problems complete with respect to a polynomial reduction? Or Logarithmic? If this too is polynomial then Reg-Complete with respect to polynomial reduction. – Craig Oct 4 '18 at 4:23
• Every non-trivial regular language (i.e., one different from $\emptyset,\Sigma^*$ is regular-complete with respect to polynomial reductions. To make the notion of completeness non-trivial, you have to choose a type of reduction which is weaker than your class. For example, NL-completeness is defined using logspace reductions, and L-completeness using first-order reductions. – Yuval Filmus Oct 4 '18 at 4:38

## 1 Answer

YES, there are.

At the beginning of "Andreas Krebs, Klaus-Jörn Lange: Dense Completeness. Developments in Language Theory 2012: 178-189"[Section 6], it is stated that some REG languages with a non-solvable monoid are complete for $$\mathrm{NC}^1$$ under $$\mathrm{DLOGTIME}$$-uniform $$\mathrm{AC}^0$$ reductions. The section goes on to state that a REG language is either in $$\mathrm{AC}^0$$ or its syntactic monoids are non-aperiodic.

Complexity Zoo states that REG is contained in $$\mathrm{NC}^1$$.

So, some REG language is complete for the class itself. This is non-trivial.