<p>If I remember correctly saw this reduction in
a paper can't find at the moment.</p>

<p>Consider the following NP-complete variation
of the Subset Sum problem.</p>

<p>Given a set of positive integers $S=\{x_1,\ldots ,x_n\}$ and
integer $t$, is there a subset of $S$ that sums to $t$?</p>

<p>There is polynomial reduction from Subset Sum to
decision if a word is in an unary language which is
Context-free grammar (CFG).</p>

<p>The unary CFG $G$ is over alphabet $\Sigma=\{1\}$ and the
productions are:</p>

<ol>
<li><p>Express powers of $2$ in unary via $B_0 \to 1, B_{2^n} \to B_{2^{n-1}} B_{2^{n-1}}$. We have $|B_{2^n}|=|B_{2^{n-1}}|+|B_{2^{n-1}}|=2|B_{2^{n-1}}|$
This is bounded by the largest $x_i$.</p></li>
<li><p>Add non terminals $X_i$ corresponding to the values of $x_i$
(after writing $x_i$ in binary)
s.t. $|X_i|=x_i$, i.e. to express $x_i = 8 + 2 + 1$ 
add $X_i \to B_8 B_2 B_1$.</p></li>
<li><p>Express the powerset of $X_i$ via the productions 
$P_1 \to \epsilon | X_1, P_n \to P_{n-1} | P_{n-1} X_n$</p></li>
<li><p>Set $S \to P_n$.</p></li>
</ol>

<p>$L(G)$ is finite and the length of words in it
correspond to the sums of the subsets in $S$.</p>

<p>The Subset Sum has solution iff $1^t \in L(G)$.</p>

<p>Not sure about this, but there is a related problem:
construct unary CFG $F$ which accepts only $1^t$ using
(1) and (2).  Set $L=L(G) \cap L(F)$. $L$ is unary
language (possibly there are Turing machines corresponding
to it). $L$ is either empty or $1^t$, which is another
reduction to Subset Sum.</p>

<p>The question:</p>

<blockquote>
  <p>In what complexity classes other than $NP$ are the
  reductions to problems related to unary language?</p>
</blockquote>

<p>According to Wikipedia and 
<a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aT#tally" rel="nofollow">Complexity Zoo</a> 
unary languages
(TALLY) do not contain NP-complete problems unless $P=NP$
and the reductions are related to NP-complete problems.
This means unary languages are not expressible enough
unless a collapse.</p>

CC BY-SA 3.0
2014-07-07T13:10:00.523Z
Just a note: subset sum is not strongly NPC, so unary subset sum is in P. In other words, when you use the unary representation of the numbers ($1^t$) in your reduction, the reduction is no more polynomial-time (i.e. is not a valid reduction to prove NP-hardness of another problem).
Marzio De Biasi
CC BY-SA 3.0
2014-07-07T13:13:30.857Z
@MarzioDeBiasi Thank you. The CFG is certainly polynomial, only the input $1^t$ is exponential in $t$, though since it is in unary it is polynomial in the input. Why Wikipedia and Complexity Zoo don't mention STRONG NPC?
joro
CC BY-SA 3.0
2014-07-07T13:26:43.890Z
I don't know :-S ... the [strongly NP-Hardness/Completeness](http://en.wikipedia.org/wiki/Strongly_NP-complete) applies only to problems involving numerical parameters, but it is quite used. Perhaps it is out of the classification scheme used by the zookeepers ... perhaps Scott Aaronson can give an answer :-)
Marzio De Biasi
CC BY-SA 3.0
2014-07-07T17:33:56.593Z
(As pointed out by Marzio De Biasi, your example isn't really an example of your question any more...) I'm not 100% clear on what you're asking, but here's one possible answer to one possible interpretation of your question. A language $L$ is poly-time reducible to a unary language if and only if $L \in \mathsf{P/poly}$.
Joshua Grochow
<cc.complexity-theory><fl.formal-languages><context-free>
In what complexity classes other than $NP$ are these problems related to unary languages?
joro
# In what complexity classes other than $NP$ are these problems related to unary languages?

(Asked by: username_0 on 2014-07-07)

If I remember correctly saw this reduction in
a paper can't find at the moment.

Consider the following NP-complete variation
of the Subset Sum problem.

Given a set of positive integers $S=\{x\_1,\ldots ,x\_n\}$ and
integer $t$, is there a subset of $S$ that sums to $t$?

There is polynomial reduction from Subset Sum to
decision if a word is in an unary language which is
Context-free grammar (CFG).

The unary CFG $G$ is over alphabet $\Sigma=\{1\}$ and the
productions are:

1. Express powers of $2$ in unary via $B\_0 \to 1, B\_{2^n} \to B\_{2^{n-1}} B\_{2^{n-1}}$. We have $|B\_{2^n}|=|B\_{2^{n-1}}|+|B\_{2^{n-1}}|=2|B\_{2^{n-1}}|$
   This is bounded by the largest $x\_i$.
2. Add non terminals $X\_i$ corresponding to the values of $x\_i$
   (after writing $x\_i$ in binary)
   s.t. $|X\_i|=x\_i$, i.e. to express $x\_i = 8 + 2 + 1$
   add $X\_i \to B\_8 B\_2 B\_1$.
3. Express the powerset of $X\_i$ via the productions
   $P\_1 \to \epsilon | X\_1, P\_n \to P\_{n-1} | P\_{n-1} X\_n$
4. Set $S \to P\_n$.

$L(G)$ is finite and the length of words in it
correspond to the sums of the subsets in $S$.

The Subset Sum has solution iff $1^t \in L(G)$.

Not sure about this, but there is a related problem:
construct unary CFG $F$ which accepts only $1^t$ using
(1) and (2). Set $L=L(G) \cap L(F)$. $L$ is unary
language (possibly there are Turing machines corresponding
to it). $L$ is either empty or $1^t$, which is another
reduction to Subset Sum.

The question:

> In what complexity classes other than $NP$ are the
> reductions to problems related to unary language?

According to Wikipedia and
[Complexity Zoo](https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aT#tally)
unary languages
(TALLY) do not contain NP-complete problems unless $P=NP$
and the reductions are related to NP-complete problems.
This means unary languages are not expressible enough
unless a collapse.

**Tags:** cc.complexity-theory, fl.formal-languages, context-free

> **Comments:**
> **username_1**: Just a note: subset sum is not strongly NPC, so unary subset sum is in P. In other words, when you use the unary representation of the numbers ($1^t$) in your reduction, the reduction is no more polynomial-time (i.e. is not a valid reduction to prove NP-hardness of another problem).  
> **username_0**: @MarzioDeBiasi Thank you. The CFG is certainly polynomial, only the input $1^t$ is exponential in $t$, though since it is in unary it is polynomial in the input. Why Wikipedia and Complexity Zoo don't mention STRONG NPC?  
> **username_1**: I don't know :-S ... the [strongly NP-Hardness/Completeness](http://en.wikipedia.org/wiki/Strongly_NP-complete) applies only to problems involving numerical parameters, but it is quite used. Perhaps it is out of the classification scheme used by the zookeepers ... perhaps Scott Aaronson can give an answer :-)  
> **username_2**: (As pointed out by username_1, your example isn't really an example of your question any more...) I'm not 100% clear on what you're asking, but here's one possible answer to one possible interpretation of your question. A language $L$ is poly-time reducible to a unary language if and only if $L \in \mathsf{P/poly}$.  

---

## 0 answers

