(a) Consider the function f: {0,1}* {0,1}* which converts binary to unary, i.e., if x is...

 

Transcribed Image Text:

(a) Consider the function f: {0,1}* {0,1}* which converts binary to unary, i.e., if x is a binary repre- sentation of an integer n, then f(x) = 1" (so for example f(101) = 11111, f(01) = 1, and f(000) = ). Is it possible to compute f in polynomial time? (b) What is wrong with the following argument? The language L=0*1* is regular, so it is in TIME(n) and thus in P. Now for any language REP, there is a reduction R (a) Consider the function f: {0,1}* {0,1}* which converts binary to unary, i.e., if x is a binary repre- sentation of an integer n, then f(x) = 1" (so for example f(101) = 11111, f(01) = 1, and f(000) = ). Is it possible to compute f in polynomial time? (b) What is wrong with the following argument? The language L=0*1* is regular, so it is in TIME(n) and thus in P. Now for any language REP, there is a reduction R