CS Talk
Dylan McKay
Host: Holly Rushmeier
Title : Can Modest Impossibility Results Resolve the P vs NP Problem?
Abstract:
For over 50 years, computer scientists have battled the P vs NP question. We do not appear to be much closer than where we started. The P vs NP question can be re-stated as the question of “is Circuit-SAT (or 3-SAT) solvable in polynomial time?” Though we have not yet even been able to prove that there is not even a linear-time algorithm for Circuit-SAT, we do know some modest impossibility results. Interestingly, one can show that algorithms which are restricted to a small amount of memory cannot solve Circuit-SAT in much faster than quadratic (n^2) time! In this talk, we give an overview of these modest impossibility results, and we juxtapose them with a theorem about the minimum circuit size problem (MCSP), showing that significantly weaker impossibility results for MCSP would resolve the P vs NP question outright.
Bio:
I grew up in Georgia, and I graduated from Georgia Tech with a BSc in Computer Science and a BSc in Discrete Mathematics. I spent the following Summer teaching Algorithms at Georgia Tech, and then I went to start my PhD at Stanford. I left with an MS in CS when my advisor and I moved to MIT, where I graduated with my PhD. I’ve since been a visiting professor at Oberlin College.