# Question about a unary language construction

For any language $L$, let us define another language $Tally(L)$, as follows: $$Tally(L)=\{1^n\;|\;\exists x \;\mbox{with}\; x\in L \;\mbox{and}\; |x|=n\}$$ That is, $Tally(L)$ encodes whether there is an $n$-bit string in $L$ or not. (Remark: there may be a standard name/notation for this construction, but I am not aware of it.)

$Tally(L)$ seems interesting for the following reasons:

1. If $L\in \mathsf{NP}$, then $Tally(L)\in \mathsf{NP}$. The reason is that one can witness $1^n\in Tally(L)$ by an $x$ with $|x|=n$ and $x\in L$, along with a polynomially sized witness $y$ for $x\in L$. Then $(x,y)$ can serve as a polynomially sized witness for $1^n\in Tally(L)$.

2. While $L\in \mathsf{NP}$ implies $Tally(L)\in \mathsf{NP}$, yet $Tally(L)$ cannot be $\mathsf{NP}$-complete, even if $L$ is $\mathsf{NP}$-complete (assuming $\mathsf{P}\neq\mathsf{NP}$). This is because $Tally(L)$ is a unary language, and it is well known that a unary (or even a sparse) language cannot be $\mathsf{NP}$-complete, if $\mathsf{P}\neq\mathsf{NP}$, due to Mahaney's Theorem (the unary version was proved earlier by Berman).

3. At the same time, it also seems unlikely that $Tally(L)\in \mathsf{P}$ for every $L\in \mathsf{NP}$. This would mean that for every $\mathsf{NP}$-property we could decide in polynomial time whether there is an $n$-bit string with the property. Or, similarly, for every graph property in $\mathsf{NP}$, no matter how complicated, we could always decide in polynomial time if there is an $n$-vertex graph with the property or not.

• I'm not sure this is a sufficiently substantial point to warrant posting as an answer, but I believe that the "Tally" construct was used in the proof that P ?= NP does not relativize. The idea is to construct a language $B$ such that $Tally(B)$ is not computed by any polynomial time machine with oracle access to $B$; then $Tally(B) \not\in P^B$, but clearly $Tally(B) \in NP^B$. So $NP^B != P^B$ while $NP^A = P^A$ for any appropriately chosen $A$ (i.e. if $A$ is any PSPACE-complete language). – Mikhail Rudoy Aug 20 '15 at 12:01