- The paper (and some sequels) that SOLVED the 17×17 problem and the 17×18 problem are now available here. The first three papers are relevent.
- There is a contest going on (it started Tuesday) INSPIRED by my 17×17 problem. In brief, they want to, for all c=2,3,4,...,21 have you find the largest n you can such that n×n can be c-colored without any monochromatic rectangles. See here for details. There is prize money! Do it for the fame AND the fortune! Deadline is Aug 31, 2012.
- (I posted this before but got no comments, so I'll just say it again.) The problem of GIVEN a partially c-colored grid does there exist a way to extend it to a c-coloring of the entire grid, is NP-complete. See
here.
Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Thursday, May 31, 2012
17x17: Paper that solved it available!/A contest inspired by it!/NPC result inspired by it!
Three new 17×17 items:
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment