Get email delivery of the Cadence blog featured here
The computational software algorithms used in EDA are fundamentally mathematical in nature. Many algorithms are various forms of computation using very large sparse matrices. Last Saturday was a significant anniversary in the foundations of mathematics.
One hundred and twenty years ago last Saturday, August 8, 1900, the German mathematician David Hilbert gave a presentation at the Sorbonne in Paris. He listed twenty-three problems in mathematics, all unsolved at the time, that would turn out to be very influential and set the agenda for much of mathematics for the early part of the twentieth century. Some were solved in the way expected by Hilbert. Some were solved, but not at all in the way that Hilbert expected, most notably Gödel's proof that mathematics could not be proved to be both consistent and complete. Some were proven unprovable. And some remain notoriously unsolved, such as the Riemann Hypothesis. Many of the problems were not actually stated precisely enough to make it clear whether subsequent work solved the problem or not. But some were resolved only in the 1970s.
Hilbert numbered the problems, so often they are known by titles like "Hlbert's 10th problem" or just "the 10th problem" if the context is obvious. There were actually 24 problems, but Hilbert dropped the 24th and it was only discovered in his original manuscript in 2000. Also, in 2000, the Clay Mathematics Institute did something similar to Hilbert's 23 problems.
Here are the first three problems, which are fairly approachable (the problems, not the solutions!):
In 2000, on May 24, the Clay Mathematics Institute proposed seven problems in mathematics and offered a million-dollar prize for solving any of them. One has been solved but the solver declined the money.
The most relevant for computer science and EDA is the P=NP problem which I wrote about in some level of detail in my post What Does P≠NP Mean?
The other six problems are:
There is a huge amount of literature about all these problems, both Hilbert's 23 problems and the Millennium Prize Problems. The Wikipedia page Hilbert's Problems is a good starting point if you want to dig deep. Of course, there's a Wikipedia page for the Millennium Prize Problems too.
If you are especially interested in the second Hilbert problem on the consistency of arithmetic, I strongly recommend computer scientist Douglas Hofstadter's tour de force 1979 book Godel, Escher, Bach (still in print).
Sign up for Sunday Brunch, the weekly Breakfast Bytes email.