Big Thinker Ron Graham Presents "Computers and Mathematics: Problems & Prospects"

NEWS
Nov 25, 2009

Professor Ronald Graham came to the Yahoo Labs campus in Santa Clara recently to demonstrate how modern computers have impacted mathematics through numerous examples from the fields of number theory, combinatorics, geometry, and computational complexity. Computers have helped mathematicians verify conjectures or find counter-examples, prove theorems, suggest new conjectures, or even new branches of mathematics. In number theory, many conjectures have been verified by computers for “small” sizes of input. For example, Goldbach’s conjecture, which claims that every even number larger than 2 can be written as the sum of two primes, has been verified for numbers up to 10^18. Reimann’s hypothesis, one of the seven “Millennium Problems” for which the Clay Mathematics Institute has offered a $1 million award, has been verified for the first 10,000,000,000,000 roots of the zeta function. Number-theoretic calculations with large numbers, such as finding large prime numbers or factoring large integers are challenging computational tasks with applications in public-key cryptosystems. The largest prime number found so far (with the help of many powerful computers) has close to 13 million digits, and the Electronic Frontier Foundation has offered a $150,000 award for discovering the first prime number of over 100 million digits. In combinatorics and graph theory, computers have been used not only to verify conjectures, but also to prove theorems and suggest new conjectures. The well-known four color conjecture, posed by Guthrie in 1852, states that every planar map can be colored with 4 colors so that no two neighboring regions are colored with the same color. This conjecture was open for over 120 years, until 1976, when it was proved by Appel and Haken with the help of a computer. The proof is based on many nice ideas and a careful case-analysis that took about 1500 hours on a mainframe. This proof has been greatly simplified since then, but to this date, no “human-readable” proof of the four color theorem is known. A computer program called Graffiti has generated some 6000 conjectures in graph theory and geometry, many of which have remained open. There are many examples in geometry where computers actually have an advantage over humans in solving the problem. For example, determining whether a knotted double torus can be unknotted (it can) is not hard for a computer, while most people try to prove that this task is impossible and fail. This is due to the fact that humans, unlike computers, approach the problem with their intuition, which is sometimes wrong. As the saying goes, the greatest obstacle to progress is not ignorance, but the illusion of knowledge. Finally, one of the most important contributions of computer science to mathematics is the development of a new branch of mathematics called complexity theory. Complexity theory investigates the boundary between problems that are computationally tractable, and those that are not. The most fundamental and the best-known problem in complexity is the P vs NP problem: can computers solve NP-complete problems such as bin packing or graph coloring in polynomial time? Most experts think that the answer is no, but no one knows how to prove this. In fact, this question is the number one problem on the Clay Mathematics Institute’s list of seven Millennium Problems with a $1 million award for a solution.

More information at:

  • http://www.research.yahoo.com/Big_Thinkers