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.(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Hard Problem (no kidding)

**Physics Forums | Science Articles, Homework Help, Discussion**