It's a challenge, good luck. :)
You should note that the instance of the problem where n= [any integer] is the P=NP problem, so don't try to solve that one. If you can give a sequence of m's where the corresponding k's increase as points in an exponential function then that would imply, though not prove, that P!=NP.
I wonder suppose i have an enormous sequence of m's and corresponding k's and the k's exhibit exponential behavior. No matter how big my sequence is, because it is finite, i can always find a polynomial that can produce those points, so this strategy will never prove P!=NP, or otherwise.
[EDIT: i take that back, for a large enough sequence you can get yourself $1 Million]