Unary language

In computational complexity theory, a unary language or tally language is a formal language (a set of strings) where all strings have the form 1^"k", where "1" can be any fixed symbol. For example, the language {1, 111, 1111} is unary, as is the language {1^"k" | "k" is prime}. The complexity class of all such languages is sometimes called TALLY.

The name "unary" comes from the fact that a unary language is the encoding of a set of natural numbers in the unary numeral system. Since the universe of strings over any finite alphabet is a countable set, every language can be mapped to a unique set A of natural numbers; thus, every language has a "unary version" {1^"k" | "k" in A}. Conversely, every unary language has a more compact binary version, the set of binary encodings of natural numbers "k" such that 1^"k" is in the language.

Since complexity is usually measured in terms of the length of the input string, the unary version of a language can be "easier" than the original language. For example, if a language can be recognized in O(2^"n") time, its unary version can be recognized in O("n") time, because "n" has become exponentially larger. More generally, if a language can be recognized in O(f("n")) time and O(g("n")) space, its unary version can be recognized in O("n" + f(log "n")) time and O(g(log "n")) space (we require O("n") time just to read the input string). However, if a problem is undecidable, then its unary version is as well.

Relationships to other complexity classes

TALLY is contained in P/poly, with a single-bit advice string for each input length "k" specifying whether 1^"k" is in the language or not. A unary language is necessarily a sparse language, since for each "n" it contains at most one value of length "n" and at most "n" values of length at most "n", but not all sparse languages are unary; thus TALLY is contained in SPARSE. Piotr Berman showed in 1978 that if any unary language is NP-complete, then P = NP, [Piotr Berman. Relationship between density and deterministic complexity of NP-complete languages. In "Proceedings of the 5th Conference on Automata, Languages and Programming", pp.63–71. Springer-Verlag. "Lecture Notes in Computer Science #62". 1978.] which Mahaney generalized to sparse languages. [S. R. Mahaney. Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis. "Journal of Computer and System Sciences" 25:130-143. 1982.]

References

* Lance Fortnow. Favorite Theorems: Small Sets. April 18, 2006. http://weblog.fortnow.com/2006/04/favorite-theorems-small-sets.html
* [http://qwiki.caltech.edu/wiki/Complexity_Zoo#tally TALLY at Complexity Zoo]