<p>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 <a href="https://cstheory.stackexchange.com/questions/16185">bounded language complete for NSPACE(log n)?</a>. For hardness in binary case, see <a href="https://cstheory.stackexchange.com/questions/8000/are-the-problems-primes-factoring-known-to-be-p-hard">Are the problems PRIMES, FACTORING known to be P-hard?</a>.</p>

<p>[1] J. Hartmanis, L. Berman, On tape bounds for single letter alphabet language processing. Theoretical Computer Science vol. 3 <a href="http://www.sciencedirect.com/science/article/pii/0304397576900244" rel="nofollow noreferrer">http://www.sciencedirect.com/science/article/pii/0304397576900244</a></p>

CC BY-SA 3.0
2013-09-13T18:20:49.437Z
2013-09-13T18:39:07.700Z
2017-04-13T12:32:28.080Z
sdcvvc
<p>Consider the language $L=\{1^n : n \text{ is prime}\}$. Is this language NLOGSPACE-Hard?</p>

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

<cc.complexity-theory><comp-number-theory><space-complexity>
Is the primality problem with unary input NLOGSPACE-Hard?
Jonathan Mosheiff
# Is the primality problem with unary input NLOGSPACE-Hard?

(Asked by: username_0 on 2013-09-13)

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.

**Tags:** cc.complexity-theory, comp-number-theory, space-complexity

---

## 1 answers

### Answer by username_1 on 2013-09-13. Score: 8 | Accepted answer

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)?](https://cstheory.stackexchange.com/questions/16185). For hardness in binary case, see [Are the problems PRIMES, FACTORING known to be P-hard?](https://cstheory.stackexchange.com/questions/8000/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>


---

