Mathematics Program and Computer Science Program Present
Climbing (or Finding Paths) through Trees: Computing the Difficulty of Mathematical Problems
Wednesday, April 5, 2023
RKC 111
12:00 pm – 1:00 pm EDT/GMT-4
12:00 pm – 1:00 pm EDT/GMT-4
Karen Lange, Wellesley College
You can make a simple family tree by starting with a person at the root and then adding two branches for her parents, and then adding two branches for the parents of each of her two parents, and so on. Such a family tree is an example of a binary tree because each level of the tree has at most two branches. We'll see that every binary tree with infinitely many nodes has an infinite path; this result is called Weak Kőnig's Lemma. But just because we know a path exists, doesn't mean we can find it. Given Weak Kőnig's Lemma, it's natural to ask whether we can compute a path through a given binary tree with infinitely many nodes. It turns out the answer to this "Path Problem" is "no", so we say that the problem is not "computable". But then what exactly is the computational power of this Path Problem?
Using the Path Problem as a test case, we will explore the key ideas behind taking a "computable" perspective on mathematics (over an "existence" one) and describe an approach for measuring the computational power of mathematical problems. We'll see that the computational power of problems varies widely and studying problems' power helps to illuminate what really makes problems "tick".
This talk will highlight ideas from graph theory, theoretical computer science, and logic, but no background in any of these subjects is necessary.
For more information, call 845-758-6822, or e-mail [email protected].
Time: 12:00 pm – 1:00 pm EDT/GMT-4
Location: RKC 111