AUC Logic Lectures: Benjamin Rin on "Computational complexity and the million dollar question!"
In 2000, the Clay Institute offered $1.000.000 to anyone who could solve any of the seven so-called Millennium Prize Problems. One of them—perhaps the most important—is the famous P/NP question. In informal terms: do there exist questions whose answers are easy (for computers) to check for correctness, but practically impossible for a computer to find?
For example, a proposed solution to a Sudoku puzzle is easy to check for correctness, even on a very large (10.000 x 10.000 or bigger) board. But finding the right solution out of all the possible combinations is impractical, even with the fastest known algorithms on the fastest of supercomputers. Is large-board Sudoku inherently impractical to solve, or might there be some way to find a solution as easily as merely checking one? This is the P/NP question.
If an answer is ever discovered, it will have profound and far-ranging implications in areas such as cryptography, games, optimisation, finance, cancer research, circuit design, philosophy, mathematical proof, artificial intelligence and so many others. The question, as well as the subfield of computer science from which it hails (computational complexity theory), also has a number of connections to logic.
|Speaker:||Dr. Benjamin G. Rin is Universitair Docent within the Theoretical Philosophy group in the Department of Philosophy and Religious Studies at Utrecht University. Primarily, his research focuses on logic and philosophy of math, and he also teaches for the artificial intelligence programme.|
Amsterdam University College
Science Park 113, 1098 XG