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!
$\begingroup$
$\endgroup$
-
$\begingroup$ Complete with respect to what kind of reduction? $\endgroup$ – Yuval Filmus Oct 4 '18 at 3:59
-
$\begingroup$ @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. $\endgroup$ – Craig Oct 4 '18 at 4:23
-
$\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 4 '18 at 4:38
$\begingroup$
$\endgroup$
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.
answered Oct 4 '18 at 4:54
