0
$\begingroup$

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 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.

$\endgroup$
  • 3
    $\begingroup$ 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). $\endgroup$ – Marzio De Biasi Jul 7 '14 at 13:10
  • $\begingroup$ @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? $\endgroup$ – joro Jul 7 '14 at 13:13
  • 1
    $\begingroup$ I don't know :-S ... the strongly NP-Hardness/Completeness 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 :-) $\endgroup$ – Marzio De Biasi Jul 7 '14 at 13:26
  • 1
    $\begingroup$ (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}$. $\endgroup$ – Joshua Grochow Jul 7 '14 at 17:33

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.