Grand Challenges, Past and Present
The history of discrete mathematics has involved a number of challenging problems which have focused attention within areas of the field. In graph theory, much research was motivated by attempts to prove the four color theorem, first stated in 1852, but not proved until 1976 (by Kenneth Appel and Wolfgang Haken, using substantial computer assistance).
In logic, the second problem on David Hilbert's list of open problems presented in 1900 was to prove that the axioms of arithmetic are consistent. Gödel's second incompleteness theorem, proved in 1931, showed that this was not possible – at least not within arithmetic itself. Hilbert's tenth problem was to determine whether a given polynomial Diophantine equation with integer coefficients has an integer solution. In 1970, Yuri Matiyasevich proved that this could not be done.
The need to break German codes in World War II led to advances in cryptography and theoretical computer science, with the first programmable digital electronic computer being developed at England's Bletchley Park. At the same time, military requirements motivated advances in operations research. The Cold War meant that cryptography remained important, with fundamental advances such as public-key cryptography being developed in the following decades. Operations research remained important as a tool in business and project management, with the critical path method being developed in the 1950s. The telecommunication industry has also motivated advances in discrete mathematics, particularly in graph theory and information theory. Formal verification of statements in logic has been necessary for software development of safety-critical systems, and advances in automated theorem proving have been driven by this need.
Computational geometry has been an important part of the computer graphics incorporated into modern video games and computer-aided design tools.
Several fields of discrete mathematics, particularly theoretical computer science, graph theory, and combinatorics, are important in addressing the challenging bioinformatics problems associated with understanding the tree of life.
Currently, one of the most famous open problems in theoretical computer science is the P = NP problem, which involves the relationship between the complexity classes P and NP. The Clay Mathematics Institute has offered a $1 million USD prize for the first correct proof, along with prizes for six other mathematical problems.
Read more about this topic: Discrete Mathematics
Famous quotes containing the words grand and/or present:
“There is the grand truth about Nathaniel Hawthorne. He says NO! in thunder; but the Devil himself cannot make him say yes. For all men who say yes, lie; and all men who say no,—why, they are in the happy condition of judicious, unincumbered travellers in Europe; they cross the frontiers into Eternity with nothing but a carpet-bag,—that is to say, the Ego. Whereas those yes-gentry, they travel with heaps of baggage, and, damn them! they will never get through the Custom House.”
—Herman Melville (1819–1891)
“To anticipate, not the sunrise and the dawn merely, but, if possible, Nature herself! How many mornings, summer and winter, before yet any neighbor was stirring about his business, have I been about mine! No doubt, many of my townsmen have met me returning from this enterprise, farmers starting for Boston in the twilight, or woodchoppers going to their work. It is true, I never assisted the sun materially in his rising, but, doubt not, it was of the last importance only to be present at it.”
—Henry David Thoreau (1817–1862)