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:

     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.


2 Answers 2


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.

  • $\begingroup$ could you please elaborate on why " Each list $L_k$ has size at most $C|\phi|^d$ "? $\endgroup$ Mar 5, 2019 at 18:40
  • $\begingroup$ Presumably because of the bound on the size of $f$’s output. $\endgroup$ Mar 5, 2019 at 19:33
  • $\begingroup$ Hello, can you expalin how it's possible to prove the invariant maintained? $\endgroup$
    – tstt
    Nov 30, 2021 at 8:46
  • $\begingroup$ That’s a nice exercise. I wouldn’t want to ruin it by spelling out the solution. $\endgroup$ Nov 30, 2021 at 9:06
  • $\begingroup$ If the initial $\phi$ is not satisfiable, wouldn't the lists become exponential in size at some point? It seems that in that case none of the $\psi_i$ would map to a unary string (because they're not satisfiable), so step 2 of the algorithm would never remove any pair. What am I missing? $\endgroup$
    – Keio203
    Nov 7, 2022 at 20:41

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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .