An MCSP Conversation Series Talk: "Computational Difficulty" by Dr. Wale Sekoni

An MCSP Conversation Series Talk: "Computational Difficulty" by Dr. Wale Sekoni

Contact: Dr. Maggie Rahmoeller, rahmoeller@roanoke.edu

A computationally difficult problem is one that cannot be solved efficiently. For modestly-sized inputs, any algorithm that solves such a problem must run for a prohibitively long time. An important class of potentially difficult problems is the set of NP-complete problems. These are problems which appear difficult in some respects but whose solutions are easy to verify. In this talk, we will look at some of these NP-complete problems. We will also look at some applications of computational difficulty, and at why proving a problem is computationally difficult might be a good thing.