tag:blogger.com,1999:blog-3722233.post7906007929863161998..comments2024-07-16T20:11:35.823-05:00Comments on Computational Complexity: Is posting about 17x17 problem BAD FOR ACADEMIA?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger29125tag:blogger.com,1999:blog-3722233.post-58880503981902259472012-02-08T07:31:20.092-06:002012-02-08T07:31:20.092-06:00the problem has been solved!
See my Feb 8, 2012 p...the problem has been solved!<br /><br />See my Feb 8, 2012 post.<br /><br />The solvers got their own paper out of it (without me)<br />and were delighted to work on it. So again, how is this<br />like a prof assigning a project for his own research?GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53503909595830682242011-03-19T08:16:59.618-05:002011-03-19T08:16:59.618-05:00I've successfully enumerated every possible pe...I'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.<br /><br />When my work is long, it can be more accurately described as:<br /><br />RIGOROUS, EXACT, DETAILED, CONSISTENT, THOROUGH, CONSCIENTIOUS, <br />METICULOUS, COMPREHENSIVE, PAINSTAKING, RELENTLESS, PROVEN, UNCOMPROMISING, DILIGENT, SYSTEMATIC, DEDICATED, CONVICTION, VIGILANT, METHODICAL, TESTED, DISCIPLINED, ALL THE VERY BEST, PERFECT.<br /><br />In one word: SCIENTIFIC.<br /><br />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.<br /><br />My program finds the first perfect coloring is seconds, and enumerates all of them, over night.<br /><br /><a href="http://www.pathcom.com/~vadco/Proposal-Email.zip" rel="nofollow">Proposal-Email.zip</a><br /><br />Explain this:<br /><br />A Perfect 10x10 3-Coloring - <br /><br />0|000|111|222|<br />-?---?---?---?-<br />0|211|221|020|<br />0|212|012|101|<br />0|221|100|211|<br />-?---?---?---?-<br />1|012|120|002|<br />1|022|201|110|<br />1|101|212|200|<br />-?---?---?---?-<br />2|102|001|021|<br />2|120|102|102|<br />2|110|020|210|<br />-?---?---?---?-<br /><br />Each row-col has a (3, 3, 4) color distribution, but the square as a whole, has the following color spread:<br /><br />34 0's<br />34 1's<br />32 2's<br /><br />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.<br /><br />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.<br /><br />Bottom line, 864 configurations are found using the above template, and 864 = 3^3x2^5, there are many less unique configurations.<br /><br />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.<br /><br />I consider myself something of an Oracle-Machine-Automaton, so I need Gasarch for NOTHING.<br /><br />I will use the Proof-Of-Concept template to solve the 17x17 problem in my own time, and share the solution with Gasarch, NEVER.<br /><br /><br />All the very best,<br /><br />JohnPaul Adamovsky<br /><br />PS - Gasarch, you have been weighed, you have been measured, and you have been found wanting.<br /><br />PPS - If you want to know who I am, look me up on Google, you genius. Then READ.<br /><br />PPPS - You are now playing "THE MANS GAME". Investigate and produce something of value, or finish crumbling.JohnPaul Adamovskyhttp://www.pathcom.com/~vadco/deep.htmlnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82387736775563236772009-12-16T23:02:22.090-06:002009-12-16T23:02:22.090-06:00If m, n, and c are given in unary, then the proble...If m, n, and c are given in <i>unary</i>, 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 <i>binary</i>, then it is not at all clear that the problem is in NP. It is certainly in NEXP.Unknownhttps://www.blogger.com/profile/07167707679832856429noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89977651064409152562009-12-14T12:23:29.221-06:002009-12-14T12:23:29.221-06:00Drake: glad we resolved this in private email.
Ev...Drake: glad we resolved this in private email.<br /><br />Everyone else: keep in mind that OBS_4 is the set of all grids that<br />axb such that axb is NOT 4-colorable but (a-1)xb and ax(b-1) are 4-colorable.<br />They are MINIMAL 4-colorable.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83540344576555131912009-12-14T11:23:52.396-06:002009-12-14T11:23:52.396-06:00Drake: YES, 19x17 is 4-colorable iff 17x19 is 4-co...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.<br />(I can't email you, I don't know your email address.) I am<br />gasarch@cs.umd.eduGASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73300929105751866952009-12-12T18:43:39.839-06:002009-12-12T18:43:39.839-06:00Forgive my ignorance, but how could 17X19 be four ...Forgive my ignorance, but how could 17X19 be four color-able, but 19X17 not?Drakehttps://www.blogger.com/profile/00447580084104857548noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33915050807247040632009-12-12T18:15:53.518-06:002009-12-12T18:15:53.518-06:00It is known that 19x17 is NOT 4-col.
Here are the ...It is known that 19x17 is NOT 4-col.<br />Here are the cases<br /><br />1) If 17x17 is NOT 4-colorable,<br />then 17x17 is in OBS4 and 17x18, 17x19 are not.<br /><br />2) If 17x17 IS 4-colorable but<br />17x18 is NOT then 17x18is in OBS4<br />but 17x17 and 17x19 are not.<br /><br />3) If 17x17 is 4-colorable and<br />17x18 is 4-colorable then<br />17x19 is in OBS4 but 17x17 and 17x18 are not.<br /><br />bill gasarchGASARCHnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25778390475383279912009-12-12T03:20:26.738-06:002009-12-12T03:20:26.738-06:00Just out of interest - in the original problem pos...Just out of interest - in the original problem post, it states that "Exactly one of the following sets is in OBS4: 19x17, 18x17, 17x17."<br /><br />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)?)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55075584393443669892009-12-11T09:09:06.196-06:002009-12-11T09:09:06.196-06:00Can a game formulation be helpful in understanding...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)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19535574404613294342009-12-10T10:58:02.148-06:002009-12-10T10:58:02.148-06:001) KURT: Actually I do not know if this is NP-comp...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<br />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).<br /><br />2) To ALL- thanks for your intelligent commentary on a post about less-than-intelligent commentary.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82781668806830115232009-12-10T10:43:15.447-06:002009-12-10T10:43:15.447-06:00The reason I REALLY THINK
17x17 IS 4-COLORABLE is...The reason I REALLY THINK <br />17x17 IS 4-COLORABLE is<br />the following:<br /><br />1) ALL of our proofs that we CANNOT c-color an nxm grid go as follows: if you<br />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<br />of size ceil(nm/c)<br /><br />2) There IS a RFS of 17x17 of size <br />ceil(289/4)+1.<br /><br />However, the more people work on it and fail to find a 4-coloring, the less confident I am.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3402100417550338812009-12-10T09:24:12.763-06:002009-12-10T09:24:12.763-06:00Stas: Sadly, it seems lpsolve at least doesn't...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.<br /><br />You can compile it using<br /><br />g++ -ldl -lm -lcolamd -I /usr/include/lpsolve/ gasarch.cc /usr/lib/liblpsolve55.a -O3<br /><br />once you have lpsolve installed (an extremely easy-to-install-and-use (and free) program for LP / mixed integer programming)<br /><br />-JelaniAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79164083167552306042009-12-10T09:18:42.095-06:002009-12-10T09:18:42.095-06:00Correction to your reminder:
It is NOT the NYU-IB...Correction to your reminder: <br />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. <br /><a href="http://www.cs.columbia.edu/theory/f09.html" rel="nofollow">See here.</a>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11515430691016157202009-12-10T07:26:55.853-06:002009-12-10T07:26:55.853-06:00That's the question whether CPLEX has a good &...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...Stashttp://www.stasbusygin.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69887695207592008932009-12-09T21:30:37.675-06:002009-12-09T21:30:37.675-06:00Stas, the linear relaxation of your IP has a trivi...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32628247183012455642009-12-09T19:52:17.631-06:002009-12-09T19:52:17.631-06:00Could you provide some more intuition as to why yo...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.<br /><br />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?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84378344969876158092009-12-09T16:04:42.566-06:002009-12-09T16:04:42.566-06:001) The problem has still not been solved. I will c...1) The problem has still not been solved. I will certainly<br />blog about it when it is.<br /><br />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.<br />Maybe he will now think twice before posting something that he cannot defend.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68500836390614011982009-12-09T14:28:52.160-06:002009-12-09T14:28:52.160-06:00Have you tried to formulate it as 0-1 programming ...Have you tried to formulate it as 0-1 programming and throw CPLEX on it? Here is a possible formulation:<br /><br />x_{ijk} = 1 if node (i,j) gets color k, 0 otherwise; i,j \in {1..17}, k \in {1..4}.<br /><br />\sum_k=1^4 x_{ijk} = 1 \forall (i,j)<br />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.<br /><br />The objective is indifferent, we need just to check if the system of constraints has a 0-1 solution.Stashttp://www.stasbusygin.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91953086884576572202009-12-09T14:13:23.894-06:002009-12-09T14:13:23.894-06:00I don't think posting about 17x17 problem &quo...I don't think posting about 17x17 problem "BAD FOR ACADEMIA" or bad for anything or else I won't blog about it.<br /><br />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.<br /><br />Best Regards,<br />Kempton<br /><br />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.kemptonhttp://kempton.ideasrevolution.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32380320822816125252009-12-09T13:38:26.700-06:002009-12-09T13:38:26.700-06:00Bill, any updates on the status of the problem? I...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59072293797800065802009-12-09T13:22:26.618-06:002009-12-09T13:22:26.618-06:00Don't forget this is effectively how functiona...Don't forget this is effectively how functional analysis got started. Banach and friends on wagering open problems.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90138538461010249272009-12-09T12:50:26.958-06:002009-12-09T12:50:26.958-06:00Either Anon 9 was a troll or he was projecting fro...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.) <br /><br />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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61985249870934968742009-12-09T12:38:29.541-06:002009-12-09T12:38:29.541-06:00Actually, thank you from the bottom of my heart fo...Actually, thank you from the bottom of my heart for posting this challenge.<br /><br />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.<br /><br />Also, I love problems that are easy to describe but hard to solve. This is a great candidate.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60431410624656526232009-12-09T12:10:55.538-06:002009-12-09T12:10:55.538-06:00A question, the problem was solved or not ?A question, the problem was solved or not ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41998478993504406012009-12-09T11:58:40.455-06:002009-12-09T11:58:40.455-06:00Anon 9 was a troll. And GASARCH, you are feeding t...Anon 9 was a troll. And GASARCH, you are feeding that troll so much rich food he/she might pop up again.Anonymousnoreply@blogger.com