tag:blogger.com,1999:blog-3722233.post3119974858044789011..comments2024-10-10T06:29:39.038-05:00Comments on Computational Complexity: Progress on R(5). Will there be more? Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-88224552077138266782024-10-02T22:59:26.570-05:002024-10-02T22:59:26.570-05:00R(4) did not require any computation time, though ...R(4) did not require any computation time, though the coloring for the lower bound took some cleverness. Past that (e.g., R(4,5)) its been really hard. For R(5) brute force won't work- even getting R(5)\le 46 took some cleverness as well as LOTS of computing time. I stand by my bet with Lance- won't be known for quite some time--- if ever.gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61123274106670413192024-10-02T22:55:58.827-05:002024-10-02T22:55:58.827-05:00Thanks for the advice- I added it.Thanks for the advice- I added it.gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11988829066581817822024-10-02T20:42:12.129-05:002024-10-02T20:42:12.129-05:00So we've got 3 or 4 data points where we have ...So we've got 3 or 4 data points where we have some idea of the computational work needed. If we graph it out, what does it look like for how much computation may be needed for R(5)<46, 45 or even 44?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-954484542869791762024-10-02T07:51:49.502-05:002024-10-02T07:51:49.502-05:00Problem
Solved
https://cdn.vox-cdn.com/thumbor/6...Problem<br /><br />Solved<br /><br />https://cdn.vox-cdn.com/thumbor/6yteUIDdQxwbFo2aHerioITCB6w=/1400x1400/filters:format(jpeg)/cdn.vox-cdn.com/uploads/chorus_asset/file/24418234/1456247036.jpg<br /><br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26472749027580289852024-09-30T13:27:16.935-05:002024-09-30T13:27:16.935-05:00Would be good to include $K_n$ is a complete graph...Would be good to include $K_n$ is a complete graph with n vertices to make the R(5) problem statement complete without prerequisites.space2001https://en.wikipedia.org/wiki/2001:_A_Space_Odysseynoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67897937961828997992024-09-30T07:29:22.778-05:002024-09-30T07:29:22.778-05:00Good point- I have added that to my postGood point- I have added that to my postgasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23512706969221733872024-09-29T23:19:58.607-05:002024-09-29T23:19:58.607-05:00Your post seems to imply that SAT solvers don'...Your post seems to imply that SAT solvers don't play a role, while they use Glucose in the paper.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.com