Consider the language $L=\{1^n : n \text{ is prime}\}$. Is this language NLOGSPACE-Hard?

The motivation for this question is that $L$ is a good candidate for reducing to other languages related to my automata research.


1 Answer 1


This language is in $\mathsf{LOGSPACE}$ via trial division. It is also known logarithmic space is neccessary ([1]). For a generalization to sparse sets, see bounded language complete for NSPACE(log n)?. For hardness in binary case, see Are the problems PRIMES, FACTORING known to be P-hard?.

[1] J. Hartmanis, L. Berman, On tape bounds for single letter alphabet language processing. Theoretical Computer Science vol. 3 http://www.sciencedirect.com/science/article/pii/0304397576900244


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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