N, As Marcus suggests, the colorful statement aims to evoke a feeling for the exploding computational complexity associated with the calculation of Ramsey numbers. The Ramsey number is interesting from a complexity perspective because it gives a condition for when to expect a particular kind of property (the existence of a clique) to manifest in a graph of relationships. What is amazing is that the values we "know" are very small and yet require a tremendous amount of computational effort to verify[5]. There are some good asymptotic bounds for larger Ramsey numbers, but in general, this problem is considered very difficult to solve. The original context where I heard Erdős speak about the problem was in the film 'N is a Number'. To some extent, the problem elucidates the value of creative thinking. There are problems of these types that no computer (and possibly no quantum computer) can hope to brute force in the lifetime of the universe and yet a mind may find a solution.
Problems like these abound in combinatorics, problems that are simple to state and have direct physical interpretations and yet give rise to tremendous complexity. I don't know much about Ramsey or his philosophy, but you'd be hard-pressed to find a mathematician that was unfamiliar with *his* number. J ps. I didn't mean to necessarily tie this idea to our discussion of *zero-knowledge protocols* though it does point to a different kind of *unknowable* perhaps, one to do with the physical limitations of computation. [5] For instance, we know that a given two-colored graph with either a red or blue pentacle has somewhere between 43 or 48 vertices, but we don't know which. Such a small number and yet... -- Sent from: http://friam.471366.n2.nabble.com/ - .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. . FRIAM Applied Complexity Group listserv Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com FRIAM-COMIC http://friam-comic.blogspot.com/ archives: http://friam.471366.n2.nabble.com/
