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?

  • 1
    $\begingroup$ 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? $\endgroup$ – Mohammad Al-Turkistany Aug 13 '15 at 4:36
  • $\begingroup$ @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. $\endgroup$ – Andras Farago Aug 13 '15 at 19:17
  • 1
    $\begingroup$ 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). $\endgroup$ – Mikhail Rudoy Aug 20 '15 at 12:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.