What is the Computational Complexity of Rearranging a Crossword Puzzle Grid?

[-Job-]

Given an n*n crossword puzzle grid composed of n^2 boxes (black and white), consider the problem of determining the size of the biggest square composed entirely of black boxes that can be created by first rearranging the rows and then the columns.
Determine the smallest k such that O(n^k) is the lower bound on the run time of any algorithm claimed to solve all instances of the above problem (with n<=m, where m is any positive integer).

This problem gets really hard as m gets bigger.

 

[dduardo]

Is this a challenge or do you need help with the problem?

 

[-Job-]

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]

 

[dduardo]

Thanks, but I don't have time to be messing with NP problems.