How do I prove Berman's theorem?
Please refer this solution. Or see the paper by S. R. Mahaney, Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis (Journal of Computer and System Sciences, 25:130-143, 1982).