(Paraphrase) Find a 4-coloring of the 17x17 grid that has
no monochromatic rectangles. For $289.00. It was solved in 2012
by Bernd Steinbach and Christian Posthoff (I posted about it
here
and will post their paper when they make it it is public, which should be soon.)
Even though it was solved, it seemed to be a hard problem.
On April 28, 2010 (before the problem was solved)
I wondered WHY it was so hard and posted the following question:
(Paraphrase) Consider the following problem:
Given (N,M,c,f) where f is a partial c-coloring of NxM,
can f be extended to a total c-coloring of NxM (without mono rectangles)?
Is this problem NP-complete?
Kevin Lawler emailed
me a sketch of a proof recently! So YES, it is NP-complete!
I cleaned it up, wrote it up, and put in a few other things, and the paper is
here.
(We will be posting to arXiv after we get comments from this blog.)
- Does this really show why the 17x17 challenge was hard?
Not really since the 17x17 challenge is just one instance.
- Does this show that grid coloring problems are hard in general?
Not really since the case we are really interesting in is where
f is the empty function. While we do not believe this case is
easy, we have not ruled this out.
- What can we show about the algorithmic complexity?
The problem is FPT. For fixed c its in time poly(N,M)+O(cc4).
While this work is very interesting
it is NOT the same as showing that finding Ramsey Numbers is hard.I suspect that to prove such things we need a new framework for
lower bounds.
Going over the paper, it appears that there's a single (or maybe just a few?) 18x18x18 solution, which has an enormous amount of special structure, and most of the smaller solutions extend from that. The step of running the simplified problem in a SAT solver was apparently only done once though, so although it took only 7 hours it's entirely possible that they got extremely lucky and running it again would take years. I'd be very curious to see the results of running it multiple times to gauge the true difficulty of that step.
ReplyDeleteSo party of the issue in this specific case may be that there was a single very well-hidden solution which needed a clever insight to be found.