Episode 10: What Use is Computational Theory?

In the last episode, we gave you the basic theory. Now we're going to show you how Computational Theory is actually used in real life. We'll discuss the various computational classes that exist and one special class in particular: NP-Complete. Using reducibility (as discussed in the previous episode) we can prove that this is a universal class of problems. This provides us evidence (but not a proof!) that many algorithms are too slow to be tractable (i.e. return a result in a useful amount of time.) Finally, we'll discuss the startling fact that some problems can't be computed at all because the laws of physics don't allow it.

Youtube version with optional visuals:

https://www.youtube.com/watch?v=rVpM8XOwmz4

Note: Due to the nature of these Computational theory episodes, it might be helpful to see the Youtube visuals.