@rgig If I understand, that would mean that there are 128 8 bit strings that are squares. There are only 128 8 bit strings with an even number of ones, so that would mean that all such stings are squares, but 10000001 obviously isn't. I'm missing something.

I had seen that before, and yes, it helps, but it does not even begin to scratch the surface of what has been proven NP-Complete. To give another example it took me much longer to find Uehara's proof that Vertex Cover was NP-complete on a 3 connected cubic planar graph than it took me to prove it. (Her proof was much cleaner than mine.)

I am interested only in m = 2. It may be that there is a one line proof, but said proof escapes me. I believe I stated that clearly in the second sentence of the question.