Hard Problem (no kidding)

  1. -Job-

    -Job- 1,132
    Science Advisor

    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.
     
  2. jcsd
  3. dduardo

    dduardo 1,919
    Staff Emeritus

    Is this a challenge or do you need help with the problem?
     
  4. -Job-

    -Job- 1,132
    Science Advisor

    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]
     
    Last edited: Oct 22, 2005
  5. dduardo

    dduardo 1,919
    Staff Emeritus

    Thanks, but I don't have time to be messing with NP problems.
     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?