tag:blogger.com,1999:blog-3722233.post3986599073640296050..comments2024-03-29T08:55:55.727-05:00Comments on Computational Complexity: W(6,2) = 1132! (excitment, not factorial)Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-57170133395707788792007-07-23T22:05:00.000-05:002007-07-23T22:05:00.000-05:00Re: Andy DShort answer is unfortunately No.Some id...Re: Andy D<BR/><BR/>Short answer is unfortunately No.<BR/>Some ideas for constructing long progression free strings are described in my paper with Dr. Franco "Resolution Tunnels for Improved SAT Solver Performance." Recently a number of people have been working on various ways to construct long progression free strings. In particular Marijn Heule, David Mitchell, ...Michal Kourilhttps://www.blogger.com/profile/10583987997544260122noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90841981666350150712007-07-22T21:48:00.000-05:002007-07-22T21:48:00.000-05:00I agree that the comment of Anonymous #2 was rude ...I agree that the comment of Anonymous #2 was rude and counterproductive.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83609840583953484552007-07-21T20:41:00.000-05:002007-07-21T20:41:00.000-05:00Ya know, Anon 2, I'm not afraid of giving my real ...Ya know, Anon 2, I'm not afraid of giving my real name while asking a stupid question -- unlike, um, some people, who #1) post anonymously and #2) "answer" a question by asking another question instead of taking a concrete position. Please note that my willingness to embrace public dopiness perhaps inspired commenter #3 to ask a question that was also "stupid" -- and now things are much clearer for a lot of us, not just me.<BR/><BR/>Have you ever done something nobody else ever did before without acting like a nitwit during the process? I haven't, and all the researchers, artists and business people I have talked to about this stuff have similar stories about having to crash through the "stupid wall" before coming up with something new.<BR/><BR/>I attended the most recent Midwest Theory Day. Do you know who asked the most (and "most obvious") questions? Lance Fortnow. In general, I think it's dumber to not ask the dumb question. As Bill asked in a recent post, which is bigger, your curiosity or your ego?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36067028164736597572007-07-20T13:42:00.000-05:002007-07-20T13:42:00.000-05:001132 is much larger than one would be led to hope ...1132 is much larger than one would be led to hope for with the most widely known elementary technique for avoiding long arithmetic progressions, namely, choosing the string randomly.<BR/><BR/>So, my question for Michal Kouril would be: does your proof suggest generalizable ideas for the construction of these progression-avoiding strings?Andy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64833120499595550192007-07-19T17:07:00.000-05:002007-07-19T17:07:00.000-05:00The result is 2 colors,you want a sequenceof lengt...The result is 2 colors,<BR/>you want a sequence<BR/>of length 6. In my<BR/>notation that I defined<BR/>above W(6,2). I regard<BR/>the sequence length as <BR/>more important.<BR/><BR/>YES W(2,k)=k+1 is trivial.<BR/>This is not what was done.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43928257913902148732007-07-19T15:08:00.000-05:002007-07-19T15:08:00.000-05:00Maybe i'm missing something here, but isn't W(2,k)...Maybe i'm missing something here, but isn't W(2,k)=k+1 trivialy true?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71742003542489890712007-07-19T14:21:00.000-05:002007-07-19T14:21:00.000-05:00Or else what? Did you think 6 colors and 2 element...Or else what? Did you think 6 colors and 2 elements???Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81170126228650913942007-07-19T13:17:00.000-05:002007-07-19T13:17:00.000-05:00Please clarify: this is for 2 colors and six eleme...Please clarify: this is for 2 colors and six elements?Anonymousnoreply@blogger.com