<p>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. (<em>Remark:</em> there may be a standard name/notation for this construction, but I am not aware of it.)</p>

<p>$Tally(L)$ seems interesting for the following reasons:</p>

<ol>
<li><p>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)$.</p></li>
<li><p>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).</p></li>
<li><p>At the same time, it also seems unlikely that $Tally(L)\in \mathsf{P}$ for <strong>every</strong> $L\in \mathsf{NP}$. This would mean that for <em>every</em> $\mathsf{NP}$-property we could decide in polynomial time whether there is an $n$-bit string with the property. Or, similarly, for <strong>every</strong> graph property in $\mathsf{NP}$, no matter how complicated,  we could <em>always</em>  decide in polynomial time if there is an $n$-vertex graph with the property or not. </p></li>
</ol>

<p><strong>Question:</strong> Is anything nontrivial known about this?</p>

CC BY-SA 3.0
2015-08-13T04:36:53.213Z
If I am not mistaken, Tally(SAT)=Tally(HornSAT). Is that what you would expect? Do you have a reason that they are not equal?
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-08-13T19:17:34.887Z
@MohammadAl-Turkistany  While I did not think about HornSAT, your comment is interesting, because it points to the issue that if L is not just any formal language, rather, it encodes a natural problem, then Tally(L) may depend not only on the problem, but also on its encoding into strings. For example, SAT and HornSAT   can both be encoded such that for every n there is an n-bit binary string which encodes a satisfiable formula. Then Tally(SAT)=Tally(HornSAT) automatically holds, but is not very informative, as it is only caused by the encoding.
Andras Farago
CC BY-SA 3.0
2015-08-20T12:01:41.327Z
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
<cc.complexity-theory><np><np-complete>
Question about a unary language construction
Andras Farago
# Question about a unary language construction

(Asked by: username_0 on 2015-08-13)

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.

**Question:** Is anything nontrivial known about this?

**Tags:** cc.complexity-theory, np, np-complete

> **Comments:**
> **username_1**: If I am not mistaken, Tally(SAT)=Tally(HornSAT). Is that what you would expect? Do you have a reason that they are not equal?  
> **username_0**: @MohammadAl-Turkistany  While I did not think about HornSAT, your comment is interesting, because it points to the issue that if L is not just any formal language, rather, it encodes a natural problem, then Tally(L) may depend not only on the problem, but also on its encoding into strings. For example, SAT and HornSAT   can both be encoded such that for every n there is an n-bit binary string which encodes a satisfiable formula. Then Tally(SAT)=Tally(HornSAT) automatically holds, but is not very informative, as it is only caused by the encoding.  
> **username_2**: 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).  

---

## 0 answers

