Unary language
Encyclopedia
In computational complexity theory
, a unary language or tally language is a formal language
(a set of strings
) where all strings have the form 1k, where "1" can be any fixed symbol. For example, the language {1, 111, 1111} is unary, as is the language {1k | 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 number
s 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 {1k | k in A}. Conversely, every unary language has a more compact binary version, the set of binary encodings of natural numbers k such that 1k 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(2n) time, its unary version can be recognized in O(n) time, because replacing every symbol with a "1" has made the language size logarithmically smaller. 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 membership in a language is undecidable
, then membership in its unary version is also undecidable.
, with a single-bit advice string for each input length k specifying whether 1k 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, which Mahaney generalized to sparse languages.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, a unary language or tally language is a formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
(a set of strings
String (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
) where all strings have the form 1k, where "1" can be any fixed symbol. For example, the language {1, 111, 1111} is unary, as is the language {1k | k is prime
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
}. The complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
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 number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s in the unary numeral system
Unary numeral system
The unary numeral system is the bijective base-1 numeral system. It is the simplest numeral system to represent natural numbers: in order to represent a number N, an arbitrarily chosen symbol representing 1 is repeated N times. For example, using the symbol | , the number 6 is represented as ||||||...
. Since the universe of strings over any finite alphabet is a countable set
Countable set
In mathematics, a countable set is a set with the same cardinality as some subset of the set of natural numbers. A set that is not countable is called uncountable. The term was originated by Georg Cantor...
, every language can be mapped to a unique set A of natural numbers; thus, every language has a unary version {1k | k in A}. Conversely, every unary language has a more compact binary version, the set of binary encodings of natural numbers k such that 1k 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(2n) time, its unary version can be recognized in O(n) time, because replacing every symbol with a "1" has made the language size logarithmically smaller. 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 membership in a language is undecidable
Recursive language
In mathematics, logic and computer science, a formal language is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the language...
, then membership in its unary version is also undecidable.
Relationships to other complexity classes
TALLY is contained in P/polyP/poly
In computational complexity theory, P/poly is the complexity class of languages recognized by a polynomial-time Turing machine with a polynomial-bounded advice function. It is also equivalently defined as the class PSIZE of languages that have a polynomial-size circuits...
, with a single-bit advice string for each input length k specifying whether 1k is in the language or not. A unary language is necessarily a sparse language
Sparse language
In computational complexity theory, a sparse language is a formal language such that the number of strings of length n in the language is bounded by a polynomial function of n. They are used primarily in the study of the relationship of the complexity class NP with other classes...
, 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
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
, then P = NP, which Mahaney generalized to sparse languages.
General references
- Lance Fortnow. Favorite Theorems: Small Sets. April 18, 2006. http://weblog.fortnow.com/2006/04/favorite-theorems-small-sets.html