99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity

Sean Carroll's Mindscape: Science, Society, Philosophy, Culture, Arts, and Ideas

Sean Carroll | Wondery

Society & Culture, Physics, Philosophy, Science, Ideas, Society

4.8 • 4.4K Ratings

🗓️ 1 June 2020

⏱️ 113 minutes

🔗️ Recording | iTunes | RSS

🧾️ Download transcript

Summary

There are some problems for which it’s very hard to find the answer, but very easy to check the answer if someone gives it to you. At least, we think there are such problems; whether or not they really exist is the famous P vs NP problem, and actually proving it will win you a million dollars. This kind of question falls under the rubric of “computational complexity theory,” which formalizes how hard it is to computationally attack a well-posed problem. Scott Aaronson is one of the world’s leading thinkers in computational complexity, especially the wrinkles that enter once we consider quantum computers as well as classical ones. We talk about how we quantify complexity, and how that relates to ideas as disparate as creativity, knowledge vs. proof, and what all this has to do with black holes and quantum gravity.

Support Mindscape on Patreon.

Scott Aaronson received his Ph.D. in computer science from the University of California, Berkeley. He is currently the David J. Bruton Jr. Centennial Professor of Computer Science at the University of Texas at Austin, and director of the Quantum Information Center there. He specializes in quantum computing and computational complexity theory, but has written on topics from free will to the nature of consciousness. Among his awards are the Tomassoni-Chisesi Prize in Physics (Italy) and the Alan T. Waterman Award from the National Science Foundation. His blog Shtetl-Optimized is known both for its humor and as the most reliable source of information on news in quantum computing. He is the author of Quantum Computing Since Democritus.

See Privacy Policy at https://art19.com/privacy and California Privacy Notice at https://art19.com/privacy#do-not-sell-my-info.

Transcript

Click on a timestamp to play from that location

0:00.0	Hello everyone, welcome to the Mindscape Podcast.
0:03.6	I'm your host Sean Carroll.
0:05.6	Here's a question of interest.
0:07.5	How hard is it to solve a problem?
0:11.4	That seems like a very important question, right?
0:13.1	Especially when we're faced with all sorts of very difficult problems, socially, biologically,
0:18.0	planetarily, and so forth.
0:19.7	But it's also a very hard question to answer in itself, right?
0:23.4	Like what do you mean?
0:24.6	How hard it is?
0:25.6	What kind of problems are you talking about?
0:27.6	Typically, computer scientists have a very specific field of problems, a specific kind
0:33.0	of problems, and they care a lot about how hard they are to solve.
0:38.4	There's a whole field of endeavor called theoretical computer science.
0:42.1	You can be a world leading theoretical computer scientist and never actually program a computer,
0:46.3	although today's guest is not in that category.
0:49.0	One of the things that theoretical computer scientists worry about is if you have a certain
0:53.0	kind of problem, like sorting a list into alphabetical order.
0:57.5	How many steps does your computer program have to take to solve that problem?
1:02.3	And how do the number of steps depend on the size of the list?
1:06.6	This is the problem known as computational complexity, and today's guest, Scott Erinzen,
1:11.5	is one of the world's experts in this field.
	...

Please login to see the full transcript.

Previous episode | Next episode

Disclaimer: The podcast and artwork embedded on this page are from Sean Carroll | Wondery, and are the property of its owner and not affiliated with or endorsed by Tapesearch.

Generated transcripts are the property of Sean Carroll | Wondery and are distributed freely under the Fair Use doctrine. Transcripts generated by Tapesearch are not guaranteed to be accurate.