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?


  • $\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

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.


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.