If an unary language exists in NPC then P=NP

Question

I've a question regarding a theorem in Complexity Theory.

It is said that if there exists an unary language in NPC then P=NP e.g if {1}* in NPC then the above is correct.

It means that there exists a Karp reduction from SAT to L, the reduction is as follows:

Let f:φ -> {1}* be the mapping function from boolean forumlas to unary strings.

Let A:{1}* -> {T,F,undefined}

We define SAT as the following algorithm:

SAT(φ,A)
     if (|φ| == 1) return φ // trivial case - True or False
     if (A(f(φ)) != undefined) return A(f(φ))
     A(f(φ)) = SAT(φ(T, x2...xn)) || SAT(φ(F, x2...xn))
     return A(f(φ))

To prove P=NP according to the assumption that there is an unary language L in NPC I need to prove the above algorithm SAT runs in polynomial time, I've been trying for two days to understand how but am lacking the knowledge, can anyone assist?

The intuition is that a string of length n has 1 representation in unary language whereas in binary languages {0,1}* it has 2^n representations.

Thanks, Max.

Answer 1

Let $L$ be an NP-complete unary language. Since $L$ is NP-complete, there is a polytime reduction $f$ from SAT to $L$. Since $f$ is polytime, $|f(x)| \leq C|x|^d$ for some $C,d$. We will now describe a polytime algorithm for SAT.

Denote the input by $\phi$, a formula on the $n$ variables $x_1,\ldots,x_n$; we assume that $|\phi| \geq n$. The algorithm proceeds in $n$ stages, creating a sequence of lists $L_n,\ldots,L_0$. The list $L_k$ consists of a list of pairs $\{(f(\psi_i),\psi_i)\}$, where $\psi_i$ is a formula resulting from substituting values for $x_{k+1},\ldots,x_n$ in $\phi$ and simplifying. We maintain the invariant that $\phi$ is satisfiable if and only if one of the $\psi_i$ is satisfiable.

The initial list $L_n$ consists of the pair $(f(\phi),\phi)$. Given the list $L_k$, we construct the list $L_{k-1}$ in two steps:

1. For each $(f(\psi),\psi) \in L_k)$, add to $L_{k-1}$ the two pairs $(f(\psi|_{x_k=\top}),\psi|_{x_k=\top})$ and $(f(\psi|_{x_k=\bot}),\psi|_{x_k=\bot})$; after substituting a value for $x_k$, we simplify the resulting formula.
2. For each $m$, out of all pairs of the form $(1^m,\psi)$ (if any) retain only one.

It is not hard to check that the invariant is indeed maintained. The final set $L_0$ could potentially contain $(f(\top),\top)$ and $(f(\bot),\bot)$; the formula is satisfiable if and only if it contains the former.

Each list $L_k$ has size at most $C|\phi|^d$, and so the algorithm runs in polynomial time.

Answer 2

The wiki page on unary languages has also that theorem on it, and a pointer to the paper by Piotr Berman.

Piotr Berman. Relationship between density and deterministic complexity of NP-complete languages. In Proceedings of the 5th Conference on Automata, Languages and Programming, pp.63–71. Springer-Verlag. Lecture Notes in Computer Science #62. 1978.

And a note: you don't have to always use SAT to when working with NP-complete problems. While it's always possible to do so, other problems may be much easier to reduce to the problem in question.