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**

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)

Loading...

Similar Threads for Hard Problem kidding | Date |
---|---|

I just erased my hard-drive and now have many problems | Apr 27, 2009 |

Hard Disk Problem | Jul 18, 2006 |

Hard drive problem | Jul 11, 2005 |

Problem with my external hard drive | Nov 20, 2004 |

Hard Drive problems? | Dec 31, 2003 |

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