computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...

, a unary language or tally language is a

formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of s ...

(a set of strings) where all strings have the form 1^''k'', where "1" can be any fixed symbol. For example, the language is unary, as is the language . The

complexity class In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms ...

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 In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called '' cardinal ...

s in the

unary numeral system The unary numeral system is the simplest numeral system to represent natural numbers: to represent a number ''N'', a symbol representing 1 is repeated ''N'' times. In the unary system, the number 0 (zero) is represented by the empty string, th ...

. Since the universe of strings over any finite alphabet is a

countable set In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural number ...

, every language can be mapped to a unique set A of natural numbers; thus, every language has a ''unary version'' . 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 membership in a language is undecidable, then membership in its unary version is also undecidable.

Relationships to other complexity classes

TALLY is contained in P/poly—the class of languages that can be recognized in polynomial time given an advice function that depends only on the input length. In this case, the required advice function is very simple—it returns a single bit for each input length ''k'' specifying whether 1^''k'' is in the language or not. A unary language is necessarily a

sparse language In computational complexity theory, a sparse language is a formal language (a set of strings) such that the complexity function, counting the number of strings of length ''n'' in the language, is bounded by a polynomial function of ''n''. They are ...

, 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. It is believed that there are no

NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

unary languages: if there exists a unary language that is

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...

, then

P = NP The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved. The informal term ''quickly'', used above ...

. This result can be extended to sparse languages. If ''L'' is a unary language, then ''L*'' (the

Kleene star In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. In mathematics, it is more commonly known as the free monoid ...

of ''L'') is a

regular language In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...

Tally classes

The complexity class P₁ is the class of the unary languages that can be recognized by a polynomial time Turing machine (given its input written in unary); it is the analogue of the class P. The analogue of NP in the unary setting is NP₁. A counting class #P₁, the analogue of #P, is also known.

Leslie Valiant Leslie Gabriel Valiant (born 28 March 1949) is a British American computer scientist and computational theorist. He was born to a chemical engineer father and a translator mother. He is currently the T. Jefferson Coolidge Professor of Compu ...

, ''The Complexity of Enumeration and Reliability Problems''

References

Notes

General references

* Lance Fortnow. Favorite Theorems: Small Sets. April 18, 2006. http://weblog.fortnow.com/2006/04/favorite-theorems-small-sets.html * {{CZoo, TALLY, T#tally Formal languages Computational complexity theory