(UPDATE- 17x17 and even 18x18 was solved. See my arXiv paper on grid colorng and/or Feb 8, 2012 post.)
(Reminder: NYU-IBM-COLUMBIA-THEORY DAY: see here.)
Anon 9 on comments on 17x17 post writes about my 17x17 post:
This is just like when teachers ask their students to model or code parts of a system that will be used in the teachers own research eventually. this is really bad for academia in general. Never again propose such things, please.I will take this comment as the starting point in an intellectually honest discussion. I reply to it after this paragraph. I then URGE the poster to reply with either: (1) Yes, GASARCH you are correct, or (2) Yes, GASARCH you are correct, but its still bad for academia because ..., or (3) No, GASARCH you are wrong because ... . Doing either would be intellectually honest. Doing neither would be intellectually dishonest. You need not use capitals or use my phrases, but you get the idea.
- When a teacher assigns students to write code for a system the students are forced to do it in order to get a good grade. I am not forcing anyone to work on the 17x17 challenge.
- When a teacher assigns students to write code for a system and the students do not get a co-authorship then this could be bad (this might depend on the situation). I stated explicitly that whoever cracks 17x17 can publish it themselves, or, if they do enough other stuff, with me. In any case the terms are out in the open. Also note that whatever I do will get much scrutiny because I posted it on a public blog rather than a private classroom.
- When a teacher assigns students to write code for a system the students might get nothing for his efforts. If a student cracks my problem they will get $289.00. If they try and fail they may learn things of interest (to be fair, this may be true for student-code-writer as well).
- The 17x17 challenge has already stimulated discussion on three blog and might get some people interested on the math end (Ramsey Theory) or the computer end. How is this bad for academia?
- As Michael pointed out what I am doing is similar to what Erdos did, though my problem is not deep mathematics. Do you think that when Erdos offered money for problems, this was bad?
- If I had posted about the problem WITHOUT the cash prize would you still object to it? (One point: if I offered it without a cash prize I would have asked to RESOLVE the problem rather than to GIVE ME a verifiable coloring). If I had offered ALOT MORE money would you object? Is it a U-shaped curve: offer either less than 10 or more than 2000 and you are okay with it? I am not being funny--- I look forward to your intelligent to comment on this.)
"This is just like when teachers ask their students to model or code parts of a system that will be used in the teachers own research eventually. this is really bad for academia in general. "
ReplyDeleteLike when Dantzig went and solved some hard homework porblems? that was terrible for all concerned...
http://en.wikipedia.org/wiki/George_Dantzig#Mathematical_statistics
I think it was a mistake to respond to Anon 9's post. Each of Anon's 3 sentences is silly, although in different ways.
ReplyDeleteTranslation: this is slightly different than the way I'm used to doing things, so I'm going to freak out about it.
ReplyDeleteI wouldn't bother with a refutation, I'd just ignore him.
(1) Yes, GASARCH you are correct
ReplyDeleteThe Anon was just a hater. This is good, it gives some motivation to solve what for most would be an uninteresting problem. Was this just one post, or where there several similarly themed opinions?
Anon 9 was a troll. And GASARCH, you are feeding that troll so much rich food he/she might pop up again.
ReplyDeleteA question, the problem was solved or not ?
ReplyDeleteActually, thank you from the bottom of my heart for posting this challenge.
ReplyDeleteI fun with a hard CS problem like this every once in a while - and this one has been good for 4 days of banging-my-head-against-different-walls-for-different-approaches fun now. Great entertainment.
Also, I love problems that are easy to describe but hard to solve. This is a great candidate.
Either Anon 9 was a troll or he was projecting from his bad experience. (Perhaps he had been asked to do something for which he wasn't given credit.)
ReplyDeleteAt any rate, I don't see anything wrong with advertising an open problem on a public blog. Any monetary award must be an addition to, but not a substitute for, due credit.
Don't forget this is effectively how functional analysis got started. Banach and friends on wagering open problems.
ReplyDeleteBill, any updates on the status of the problem? I'm somewhat surprised that using a SAT-solver didn't work to find a coloring, because it seems like the 17x17 case ought to be small enough for that approach to be successful. Am I safe in assuming that the problem of finding a c-coloring for an nxn grid is NP-complete? (I apologize, I haven't read any of the background materials you referenced.) The boundary cases like 17x17 or 18x18 for c=4 must be right in the sweet spot between being underconstrained and overconstrained.
ReplyDeleteI don't think posting about 17x17 problem "BAD FOR ACADEMIA" or bad for anything or else I won't blog about it.
ReplyDeleteI hope we will have a solution to your 17 x 17 problem soon and I hope we can learn something from the solution. If nothing else, it will be fun to see you pay up on that $289 prize.
Best Regards,
Kempton
P.S. My apologies to GASARCH and thanks for pointing out my mistake in the blog entry. I've made a correction to "Prize offered by" section, it is now listed with GASARCH only.
Have you tried to formulate it as 0-1 programming and throw CPLEX on it? Here is a possible formulation:
ReplyDeletex_{ijk} = 1 if node (i,j) gets color k, 0 otherwise; i,j \in {1..17}, k \in {1..4}.
\sum_k=1^4 x_{ijk} = 1 \forall (i,j)
x_{i_1 j_1 k} + x_{i_1 j_2 k} + x_{i_2 j_1 k} + x_{i_2 j_2 k} \leq 3 \forall (i_1, j_1, i_2, j_2, k), i_1 \neq i_2, j_1 \neq j_2.
The objective is indifferent, we need just to check if the system of constraints has a 0-1 solution.
1) The problem has still not been solved. I will certainly
ReplyDeleteblog about it when it is.
2) I did this blog to SEE if Anon 9 had anything intelligent to say. While I am not surprised that he did not, I was curious.
Maybe he will now think twice before posting something that he cannot defend.
Could you provide some more intuition as to why you "REALLY REALLY THINK THAT IT IS 4-COLORABLE"? At the moment it seems (for me) equally likely that there is no solution.
ReplyDeleteI saw your conjecture in the paper, but despite that it holds for most cases, what more evidence is there suggesting that it should hold for 17x17 as well?
Stas, the linear relaxation of your IP has a trivial solution where all variables are set to 1/4. CPLEX won't do anything here that a pure constraint solver couldn't.
ReplyDeleteThat's the question whether CPLEX has a good "pure constraint" satisfaction (feasibility) routine. Clever use of cutting planes can help a lot in this kind of problems. I'd give it a try but don't have access to CPLEX for free anymore...
ReplyDeleteCorrection to your reminder:
ReplyDeleteIt is NOT the NYU-IBM theory day... COLUMBIA is one of the organizers! In fact, theory day apparently started by Zvi Galil of Columbia years ago, with NYU/IBM joining later.
See here.
Stas: Sadly, it seems lpsolve at least doesn't. The code at http://web.mit.edu/minilek/www/gasarch.cc gets pretty slow even to 5 color a 10x10 grid.
ReplyDeleteYou can compile it using
g++ -ldl -lm -lcolamd -I /usr/include/lpsolve/ gasarch.cc /usr/lib/liblpsolve55.a -O3
once you have lpsolve installed (an extremely easy-to-install-and-use (and free) program for LP / mixed integer programming)
-Jelani
The reason I REALLY THINK
ReplyDelete17x17 IS 4-COLORABLE is
the following:
1) ALL of our proofs that we CANNOT c-color an nxm grid go as follows: if you
could c-color nxm then there would be a Rectangle free set of size ceil(nm/c). We then show that there is NO RFS
of size ceil(nm/c)
2) There IS a RFS of 17x17 of size
ceil(289/4)+1.
However, the more people work on it and fail to find a 4-coloring, the less confident I am.
1) KURT: Actually I do not know if this is NP-complete. It might NOT be since there isn't much structure. My GUESS: the problem of GIVEN a PARTIALLY colored grid can it be extended is NPC, but the problem of just given
ReplyDeleten,m,c (in binary) is not NPC. GOOD OPEN PROBLEM: Proof its NPC or show that if its NPC then bad things happen (e.g., PH collapses).
2) To ALL- thanks for your intelligent commentary on a post about less-than-intelligent commentary.
Can a game formulation be helpful in understanding the intricacies (or as the exploit human computing to prove)- two players alternately color the grid points. The first one to get a rectangle of the same color loses - (using at most four colors)
ReplyDeleteJust out of interest - in the original problem post, it states that "Exactly one of the following sets is in OBS4: 19x17, 18x17, 17x17."
ReplyDeleteDoesn't that imply that only 17x17 at most is in OBS4 (because if there was a 4-coloring for 19x17, there would be both 18x17 and 17x17 4-colorable subsets (and so forth for 17x17 being a subset of 18x17)?)
It is known that 19x17 is NOT 4-col.
ReplyDeleteHere are the cases
1) If 17x17 is NOT 4-colorable,
then 17x17 is in OBS4 and 17x18, 17x19 are not.
2) If 17x17 IS 4-colorable but
17x18 is NOT then 17x18is in OBS4
but 17x17 and 17x19 are not.
3) If 17x17 is 4-colorable and
17x18 is 4-colorable then
17x19 is in OBS4 but 17x17 and 17x18 are not.
bill gasarch
Forgive my ignorance, but how could 17X19 be four color-able, but 19X17 not?
ReplyDeleteDrake: YES, 19x17 is 4-colorable iff 17x19 is 4-colorable. Where do I say otherwise? Feel free to email me commenting since I might not check comments that often.
ReplyDelete(I can't email you, I don't know your email address.) I am
gasarch@cs.umd.edu
Drake: glad we resolved this in private email.
ReplyDeleteEveryone else: keep in mind that OBS_4 is the set of all grids that
axb such that axb is NOT 4-colorable but (a-1)xb and ax(b-1) are 4-colorable.
They are MINIMAL 4-colorable.
If m, n, and c are given in unary, then the problem is probably not NPC, because it Karp reduces to a tally set (so NPC-ness under Karp reductions implies P=NP by Mahaney). If m, n, and c are given in binary, then it is not at all clear that the problem is in NP. It is certainly in NEXP.
ReplyDeleteI've successfully enumerated every possible perfect 10x10 3-Coloring, using a novel and dazzling algorithm, as a Proof-Of-Concept for solving the 17x17 problem. In response to my proposal, requiring a 24 thread machine, William Gasarch said it was long, so he wasn't interested in reading it.
ReplyDeleteWhen my work is long, it can be more accurately described as:
RIGOROUS, EXACT, DETAILED, CONSISTENT, THOROUGH, CONSCIENTIOUS,
METICULOUS, COMPREHENSIVE, PAINSTAKING, RELENTLESS, PROVEN, UNCOMPROMISING, DILIGENT, SYSTEMATIC, DEDICATED, CONVICTION, VIGILANT, METHODICAL, TESTED, DISCIPLINED, ALL THE VERY BEST, PERFECT.
In one word: SCIENTIFIC.
I will now give you a link to the entire email I send to William Gasarch with my proposal, so you can judge for yourself, if the program, I took it upon myself to write for him, is the most powerful algorithm ever coded to solve this class of problem.
My program finds the first perfect coloring is seconds, and enumerates all of them, over night.
Proposal-Email.zip
Explain this:
A Perfect 10x10 3-Coloring -
0|000|111|222|
-?---?---?---?-
0|211|221|020|
0|212|012|101|
0|221|100|211|
-?---?---?---?-
1|012|120|002|
1|022|201|110|
1|101|212|200|
-?---?---?---?-
2|102|001|021|
2|120|102|102|
2|110|020|210|
-?---?---?---?-
Each row-col has a (3, 3, 4) color distribution, but the square as a whole, has the following color spread:
34 0's
34 1's
32 2's
Pick up on this pattern: Of the 2 colors with a 34 count, each (4-count) row intersects with a (4-count) col of the same color.
From the top-left to bottom right, there are 9 enumerated sets, which must be internally rectangle free, and must not rectangle with the static row and column. Further, set 0, 4, and 8 are limited to an in-order "Permutation 0" configuration.
Bottom line, 864 configurations are found using the above template, and 864 = 3^3x2^5, there are many less unique configurations.
You got valid color-swaps, valid column shuffles, valid (4-4 Intersect) flips, and row-col exchange. Testing for uniqueness is not a trivial exercise, so I am leaving for each, his own.
I consider myself something of an Oracle-Machine-Automaton, so I need Gasarch for NOTHING.
I will use the Proof-Of-Concept template to solve the 17x17 problem in my own time, and share the solution with Gasarch, NEVER.
All the very best,
JohnPaul Adamovsky
PS - Gasarch, you have been weighed, you have been measured, and you have been found wanting.
PPS - If you want to know who I am, look me up on Google, you genius. Then READ.
PPPS - You are now playing "THE MANS GAME". Investigate and produce something of value, or finish crumbling.
the problem has been solved!
ReplyDeleteSee my Feb 8, 2012 post.
The solvers got their own paper out of it (without me)
and were delighted to work on it. So again, how is this
like a prof assigning a project for his own research?