Sep 28, 2007
Algorithms and complexity on the borderline of mathematics and computer science
Zoltan Szekely
Do you want to earn one million dollar by problem solving? Then have a look at the open problem list of the Clay's Mathematical Institute. Solution for any of them is rewarded by a prize of one million dollar! Many of these problems are related to algorithms and complexity theory. This talk will focus on challenging problems that are common interest in mathematics and computer science, including the Hamiltonian Circuit, the Vertex Coloring and other NP-complete problems and the Road Coloring Problem.
---------------------------------
Oct 26, 2007
"P=NP?" -- on the borderline of mathematics and computer science
Zoltan Szekely
The Clay's Mathematical Institute established a one million dollar prize for anyone who solves any of the so called Millennium Prize Problems. One problem on this list is the famous "P=NP?" question. In this talk we'll cover the basics to understand this question in its full deepness, and discuss the relevant algorithmic problems as related to computational complexity (Traveling Salesman problem, Clique problem, Cook's Theorem, etc.). We'll discuss how we can transform algorithms with known complexities into other algorithms establishing their own complexity measure. This way we obtain classes of algorithms with equivalent complexities. The technique may also provide a tool of solving the "P=NP" question, and thus win the one million dollar prize!
---------------------------------
|
|
|