Take the 2-minute tour ×

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.

share|improve this question

1 Answer 1

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.

share|improve this answer

Your Answer


