Theory of Anything Podcast 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.