Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.