# If an unary language exists in NPC then P=NP

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.

-