# Complexity classes for problems that can be solved only from the length of the input

A tally language is a language on an alphabet with only one symbol. One can define complexity classes for tally languages, such as $P_1$ (the tally languages that can be decided in polynomial time).

Consider the non-unary alphabet $A = \{0, 1\}$. Say I have a language $L$ on $A$ such that there is a unary language $L_1$ on the singleton alphabet $\{1\}$ with $L = \{w \in A^* \mid 1^{|w|} \in L_1\}$. In other words, $L$ is the language of words on $A$ whose length (written as a string of $1$'s) is in $L_1$.

The language $L$ is not a tally language, because it is not on a unary alphabet. Intuitively, however, it's not very far from being one: it can be decided only from the length of the input, or in other words it is a tally language "up to remapping the alphabet". Is there a standard name for such a language?

Further, if I consider the class of all such languages on $A$, for tally languages that range in a given tally complexity class (say, $P_1$), is there a standard name for the resulting non-tally class?

• So, simply the closure of the class under inverse length-preserving morphisms, right? – Michaël Cadilhac Nov 4 '15 at 21:18
• @MichaëlCadilhac: Yes, I guess that's one way to say it. – a3nm Nov 4 '15 at 21:56
• Every tally language is sparse, but not all non-tally languages (as you define them) are sparse. If $C$ is a tally complexity class, the corresponding non-tally class is included in $C/poly$. – Boson Nov 5 '15 at 8:18