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!
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityI 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!
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.