Editing Discrete mathematics (section)

==Challenges==
[[File:Four Colour Map Example.svg|thumb|180px|right|Much research in [[graph theory]] was motivated by attempts to prove that all maps, like this one, can be [[graph coloring|colored]] using [[four color theorem|only four colors]] so that no areas of the same color share an edge. [[Kenneth Appel]] and [[Wolfgang Haken]] proved this in 1976.<ref name="4colors">{{cite book| last = Wilson| first = Robin| author-link = Robin Wilson (mathematician)| title = Four Colors Suffice| year = 2002| publisher = Penguin Books| isbn = 978-0-691-11533-7| place = London| url-access = registration| url = https://archive.org/details/fourcolorssuffic00wils}}</ref>]]

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).<ref name="4colors" />

In [[Mathematical logic|logic]], the [[Hilbert's second problem|second problem]] on [[David Hilbert]]'s list of open [[Hilbert's problems|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 [[Matiyasevich's theorem|could not be done]].

The need to [[Cryptanalysis|break]] German codes in [[World War II]] led to advances in [[cryptography]] and [[theoretical computer science]], with the [[Colossus computer|first programmable digital electronic computer]] being developed at England's [[Bletchley Park]] with the guidance of [[Alan Turing]] and his seminal work, [[On Computable Numbers]].<ref>{{cite book| last=Hodges | first=Andrew | author-link=Andrew Hodges | title=[[Alan Turing: The Enigma]] | publisher=[[Random House]] | year=1992 }}</ref> The [[Cold War]] meant that cryptography remained important, with fundamental advances such as [[public-key cryptography]] being developed in the following decades. The [[telecommunications 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 system]]s, and advances in [[automated theorem proving]] have been driven by this need.

[[Computational geometry]] has been an important part of the [[Computer graphics (computer science)|computer graphics]] incorporated into modern [[video game]]s 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 [[Phylogenetic tree|tree of life]].<ref>{{cite book| first1 = Trevor R. |last1=Hodkinson |first2=John A. N. |last2=Parnell| title = Reconstruction the Tree of Life: Taxonomy And Systematics of Large And Species Rich Taxa| url = https://books.google.com/books?id=7GKkbJ4yOKAC&pg=PA97| year = 2007| publisher = CRC Press | isbn = 978-0-8493-9579-6| page = 97 }}</ref>

Currently, one of the most famous open problems in theoretical computer science is the [[P = NP problem]], which involves the relationship between the [[complexity class]]es [[P (complexity)|P]] and [[NP (complexity)|NP]]. The [[Clay Mathematics Institute]] has offered a $1 million [[USD]] prize for the first correct proof, along with prizes for [[Millennium Prize Problems|six other mathematical problems]].<ref name="CMI Millennium Prize Problems">{{cite web|title=Millennium Prize Problems|url=http://www.claymath.org/millennium/|date=2000-05-24|access-date=2008-01-12}}</ref>