RSS icon
Twitter icon
Facebook icon
Vimeo icon
YouTube icon

The limits of computation

JQI Podcast Episode 13
Credit: Yuri Samoilov/CC BY 2.0

Modern computers, which dwarf their forebears in speed and efficiency, still can't conquer some of the hardest computational problems. Making them even faster probably won't change that.

Computer scientists working in the field of computational complexity theory explore the ultimate limits of computers, cataloguing and classifying a universe of computational problems. For decades, they’ve been stuck on a particular nagging question, which boils down to this: What’s the relationship between solving a problem and checking your work?

Chris Cesare teams up with Emily Edwards and QuICS postdoctoral researcher Bill Fefferman to explain what this question entails and how researchers are tackling it with tools from physics.

This episode of Relatively Certain was produced and edited by Chris Cesare, with contributions from Emily Edwards, Sean Kelley and Kate Delossantos. It features music by Dave Depper, Podington Bear, Kevin MacLeod and Little Glass Men. Relatively Certain is a production of the Joint Quantum Institute, a research partnership between the University of Maryland and the National Institute of Standards and Technology, and you can find it on iTunes, Google Play or Soundcloud.

Recent Podcast Episodes

Photo of a diamond chip NV experiment

We all know that diamonds can hold great sentimental (and monetary) value. As luck may have it, diamonds—particularly defective ones, with little errors in their crystal structure—also hold great scientific value.

An artist's depiction of an atom sitting on a representation of a warped spacetime

Gravity is a fixture of our everyday lives, particularly apparent when we drop a piece of toast on the kitchen floor or trip over an unseen step. Not surprisingly, physicists have studied gravity heavily over the centuries.

An artists's rendering of an atom with galaxies embedded inside

There’s a big unsolved mystery in physics: The cosmic balance sheet for matter in our universe just doesn’t add up. Galaxies all over space move as though they are much heavier than they appear.