This work is licensed under a
Creative Commons License.
|
Wednesday, December 09, 2009
Is posting about 17x17 problem BAD FOR ACADEMIA?
Posted by GASARCH
(The 17x17 problem has gotten far wider attention than I imagined--- Brian Hayes posted it on his website: here, and its also here and here. The last website is odd in that it mentions my co-authors as also putting up the money, which is not true.)
(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.)
11:07 AM
# 27 comments
-
"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. "
Like 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.
-
Translation: this is slightly different than the way I'm used to doing things, so I'm going to freak out about it.
I wouldn't bother with a refutation, I'd just ignore him.
-
(1) Yes, GASARCH you are correct
The 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.
-
A question, the problem was solved or not ?
-
Actually, thank you from the bottom of my heart for posting this challenge.
I 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.)
At 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.
-
Bill, 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.
-
I don't think posting about 17x17 problem "BAD FOR ACADEMIA" or bad for anything or else I won't blog about it.
I 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:
x_{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
blog 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.
I 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.
-
That'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...
-
Correction to your reminder:
It 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.
You 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
17x17 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
n,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)
-
Just out of interest - in the original problem post, it states that "Exactly one of the following sets is in OBS4: 19x17, 18x17, 17x17."
Doesn'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.
Here 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?
-
Drake: 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.
(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.
Everyone 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.
Links to this post:
Weblog Home
Archives
