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 - The Fusion of Science and Community**

# Hard Problem (no kidding)

Know someone interested in this topic? Share a link to this question via email,
Google+,
Twitter, or
Facebook

Have something to add?

- Similar discussions for: Hard Problem (no kidding)

Loading...

**Physics Forums - The Fusion of Science and Community**