Ramsey Numbers: A Problem of Galactic Proportions

davidamos.dev

8 pointsColinWright4 comments

>you need to check 2^903 edge colorings

This instantly reminded me of the "It will never be possible to brute force AES256 (Check 2^256 possibilities) because, even in the best case, it needs more energy than the whole Solar system contains" [0] The author states that 2^903 should be possible to do in less than a year. Am I wrong and those aren't related problems? Or is the author a bit optimistic?

[0] https://security.stackexchange.com/a/6149

The problem has plenty of symmetry and there are ways to solve it other than naive brute force. For example, the proof that R(3,3)=6 is given in the first part of the article, and does not involve listing 2^15 graphs.

This also could apply to AES256 - if it has some mathematical structure that can be exploited, then brute forcing might not be needed to break it - see https://en.wikipedia.org/wiki/Advanced_Encryption_Standard#K... .

True but the last part of the article is basically only about the computation and not about mathematical breakthroughs. And from that point of view both numbers are equally infeasible to compute right?

These numbers are nothing compared to https://en.wikipedia.org/wiki/Busy_beaver

Reply on news.ycombinator.com