YouSaid · the spoken record

Scott Aaronson

lines on the record: 134
first: 2020-10-12
most recent: 2020-10-12
sittings or episodes: 1
sources: podcast

Every line below is reproduced as it was said and linked to the record it came from. Nothing here is summarised or generated. Directory · Search · Corrections

“There was this great cartoon. I think it was one of the classic XKCDs where it shows a heart and it's like, you know, squaring the heart, taking the Fourier transform of the heart, you know, integrating the heart each thing. And then it says, you know, my normal approach is useless here.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“I love my kids. I love my wife. I love my parents. You know, I am probably not different from most people in loving their families and in that being very important in my life. Now, I should remind you that I am a theoretical computer scientist. If you're looking for deep insight about the nature of love, you're probably looking in the wrong place to ask me. But sure, it's been important.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“It does. It does. But yeah, I mean, in terms of what is the solution, I mean, I wish I knew, right? And so, you know, in a certain way, these problems are maybe harder than P versus NP, right? I mean, you know, but I think that part of it has to be for, you know, that I think that there's a lot of sort of silent support for what I'll call the open discourse side, the reasonable enlightenment side. And I think that that support has to become less silent, right? I think that a lot of people that sort of, you know, like agree that, you know, a lot of these cancellations and attacks are ridiculous, but are just afraid to say so, right? Or else they'll get shouted down as well, right? That's just the standard witch hunt dynamic, which, you know, of course, this, you know, this faction understands and exploits to its great advantage.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Yeah. I don't think I can. Yeah, I've gotten to know Steve a bit. He is incredibly unperturbed by this stuff. And I admire that and I envy it. I wish that I could be like that. I mean, my impulse when I'm getting attacked is I just want to engage every single like anonymous person on Twitter and Reddit who is saying mean stuff about me. And I want to just say, look, look, can we just talk this over for an hour? And then, you know, you'll see that I'm not that bad. And, you know, sometimes that even works. The problem is then there's the, you know, the $20,000 other ones.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Thoughtful about difficult topics, he does. Well, I mean, I mean, yes, but it's also amazing how well Steve has withstood it. I mean, he just survived that attempt to cancel him just a couple of months ago, right? Psychologically.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Those terms to say, well, then you have to agree with all of these other extremely contentious positions, or else you are a misogynist, or else you are a racist, right? I say that, well, no, you know, don't like. Don't I, or don't people like me also get a say in the discussion about, you know, what is racism, about what is going to be the most effective to combat racism, right? And this cancellation mentality, I think, is spectacularly ineffective at its own professed gall of combating racism and sexism.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Well, look, I mean, to say that I am opposed to this trend or of shouting people down rather than engaging them, that would be a massive understatement, right? And I feel like, you know, I have. Put my money where my mouth is, not as much as some people have, but I've tried to do something. I mean, I have defended some unpopular people and unpopular ideas on my blog. I've tried to defend norms of open discourse, of reasoning with our opponents, even when I've been shouted down for that on social media, you know, called a racist, called a sexist, all of those things, which, by the way, I should say, you know, I would be perfectly happy to, you know, say, you know, if we had time to say, you know, 10,000 times, you know, my hatred of racism, of sexism, of homophobia, right? But what I don't want to do is to cede to some particular political faction the right to define exactly what is meant.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Aside. And that's oh, I know there are because I know some of them, yeah, right? I mean, you know, it's still, you know, maybe it baffles me, but, you know, I know such people.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Yeah Yeah, well, look, I mean, it's been said by others that this is the first time in the country's history that we have a president who does not even pretend to want to unite the country, right? And I mean, Lincoln, who fought a civil war, you know, you know, said he wanted to unite the country, right? And I do worry enormously about what happens if the results of this election are contested. And will there be violence as a result of that? And will we have a clear path of succession? And you know, look, I mean, you know, this is all we're going to find out the answers to this in two months. And if none of that happens, maybe I'll look foolish. But I am willing to go on the record and say, I am terrified about that.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Y Well, I mean, I'm as surprised as almost everyone else. I mean, this is a historic failure. It is one of the biggest failures in the 240-year history of the United States. And we should be Crystal clear about that. And one thing that I think has been missing, even from the more competent side is like, you know, is sort of the World War II mentality, right? The mentality of let's just by breaking a whole bunch of rules get a vaccine and even half the amount of time as we thought, then let's just do that because, you know, like we have to weigh all of the moral qualms we have about doing that against the moral qualms of not doing.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“I thought that each month that a vaccine is closer is like trillions of dollars. Are you surprised and of course lives hundreds of thousands of lives?”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“It's not going to fix everything, but it's like I feel like there's a ship that is sinking and you could at least stop the sinking. But I think that there are much, much deeper problems. I mean, I think that it is plausible to me that, you know, a lot of the failures with the CDC, with some of the other health agencies, even, you know, predate Trump, you know, predate the right-wing populism that has sort of taken over much of the world now. And, you know, I think that, you know, it was very, I'm actually, you know, I've actually been strongly in favor of rushing vaccines, of, you know, I thought that we could have done human challenge trials, you know, which were not done, right? We could have, you know, I had volunteers to actually be get vaccines, get exposed to COVID.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“You know, yeah, they're the best of the best. And there are these conspiracy theorists who think, you know, this is all fake news. There's not really a pandemic. And those are some random people on the internet who are the hypercompetent government people have to, you know, oppose, right? In trying to envision the worst thing that could happen, like, you know, there was a failure of imagination. The movie makers did not imagine that the conspiracy theorists and the incompetence and the nut cases would have captured our institutions and be the ones actually running things.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“An airborne virus originates in China, spreads to much of the world, shuts everything down until a vaccine can be developed. Everyone has to stay at home. It gets an enormous number of things right. But the one thing that they could not imagine, you know, is that in this movie, everyone from the government is like hyper competent, hyper, you know, dedicated to the public good, right? Best of the best.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Yeah, well, I mean, all of our lives have changed as with no other event since I was born. You would have to go back to World War II for something, I think, of this magnitude on the way that we live our lives. As for how it has changed my worldview, I think that the failure of institutions like the CDC, like other institutions that we sort of thought were trustworthy, like a lot of the media was staggering, was absolutely breathtaking. It is something that I would not have predicted. I think I wrote on my blog that, you know, it's fascinating to rewatch the movie contagion from a decade ago, right? That correctly foresaw so many aspects of, you know, what was going on.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Fascinating. So, yeah, so SDK is all of the problems that have protocols like that one, but it has this beautiful other characterization. It's shown up again and again in my own work, in a lot of people's work. And I think that it really is one of the most fundamental classes. It's just that people didn't realize that when it was first discovered”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Yeah, and let's say that that wizard did that a hundred times and it was right every time. Right now, if the graphs were isomorphic, then it would have been flipping a coin each time, right? It would have had only a one and two to the 100 power chance of, you know, of guessing right each time. But so if it's right every time, then now you're statistically convinced that these graphs are not isomorphic, even though you've learned nothing new about why they are.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“SDK is all of the problems for which there is such a proof that doesn't rely on any cryptography. And if you wonder how could such a thing possibly exist, right? Well, like imagine that I had two graphs and I wanted to convince you that these two graphs are not isomorphic, meaning I cannot permute one of them so that it's the same as the other one, right? You know, that might be a very hard statement to prove, right? I might, you know, you might have to do a very exhaustive enumeration of, you know, all the different permutations before you were convinced that it was true. But what if there were some all-knowing wizard that said to you, look, I'll tell you what, just pick one of the graphs randomly, then randomly permute it, then send it to me, and I will tell you which graph you started with. And I will do that every single time, right?”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“SDK problem. And the way that this class was originally discovered was completely different from that and was kind of more complicated. It was discovered as the class of all of the problems that have a certain kind of what's called zero knowledge proof. Zero knowledge proofs are one of the central ideas in cryptography. You know, Shafi Goldwasser and Silvio McCauley won the Touring Award for inventing them. And they're at the core of even some cryptocurrencies that people use nowadays. Zero knowledge proofs or ways of proving.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Know if you're asking what's there's a class that I think is way more beautiful than or fundamental than a lot of people even within this field realize that it is that class is called SDK or statistical zero knowledge And there's a very, very easy way to define this class, which is to say, suppose that I have two algorithms that each sample from probability distributions, right? So each one just outputs random samples according to possibly different distributions. And now the question I ask is, you know, let's say distributions over strings of n bits, so over an exponentially large space. Now I ask, are these two distributions close or far as probability distributions? Okay, any problem that can be reduced to that, you know, that can be put into that form is an”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Such a state would be exponentially hard to prepare. Okay, but maybe somehow these states were formed in the Big Bang or something and they've just been sitting around ever since, right? If you found one, and if this state could be like ultra power, there are no limits on how powerful it could be, except that this state doesn't know in advance which input you've got, right? It only knows the size of your input, you know, and then that's BQP slash QPoly. So that's one that I just personally happen to love, okay?”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“I used as my email address BQPQPoly at gmail.com just because bq slash qpoly well you know amazingly no one had taken it amazing amazing but you know but this is a class that i was involved in sort of defining proving the first theorems about uh in 2003 or so so it was kind of close to my heart uh but this is like if we extended um bq which is the class of everything we can do efficiently with a quantum computer to allow quantum advice which means imagine that you had some special initial state okay that could somehow help you do computation and maybe um”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Okay, so that's an exponentially large sum, but I can calculate it just reusing the same memory over and over for each term in the song.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“And just explicitly calculate each of these amplitudes, right? You know, that will be very inefficient, but it will work, right? It's enough to show that quantum computers could not solve the halting problem. Or, you know, they could never do anything that is literally uncomputable in Turing sense. But now, as I said, there is even a stronger result, which says that BQP is contained in PSpace. The way that we prove that is that we say if all I want is to calculate the probability of some particular output happening, which is all I need to simulate a quantum computer, really, then I don't need to write down the entire quantum state, which is an exponentially large object. All I need to do is just calculate what is the amplitude for that final state. And to do that, I just have to sum up all the amplitudes that lead to that state.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Okay, so I just summarized quantum mechanics in like 30 seconds. Okay. But now what this already tells us is that anything I can do with a quantum computer, I could simulate with a classical computer if I only have exponentially more time. Okay, and why is that? Because if I have exponential time, I could just write down this entire branching tree.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“But yeah, we did last time. But basically, you can always think of a quantum computation as like a branching tree of possibilities where each possible path that you could take through the space has a complex number attached to it called an amplitude. And now the rule is when you make a measurement at the end, will you see a random answer? But quantum mechanics is all about calculating the probability that you're going to see one potential answer versus another one, right? And the rule for calculating the probability that you'll see some answer is that you have to add up the amplitudes for all of the paths that could have led to that answer. And then, you know, that's a complex number so that how could that be a probability? Then you take the squared absolute value of the result. That gives you a number between 0 and 1.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Oh, that's an excellent question. So there is, well, I mean, one has to prove that. But the proof you could think of it as using Richard Feynman's picture of quantum mechanics, which is that you can always, you know, we haven't really. Talked about quantum mechanics in this conversation. We did in our previous”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“P is contained in BPP, which is contained in BQP, which is contained in P-Space. So anything you can, in fact, in something very similar to sharp p. BQP is basically, you know, well, it's contained in like P with the magic power to solve Sharp P problems. Why?”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Unfortunately, it seems not, or certainly not yet, right? The techniques that we use to establish those things, they're very, very related to how Turing proved the unsolvability of the halting problem, but they seem to break down when we're comparing two different resources, like time versus space or like, you know, P versus NP. Okay, but there's what you can do with a randomized algorithm, right? That can sometimes, you know, has some probability of making a mistake. That's called BPP, bounded error probabilistic polynomial time. And then, of course, there's one that's very close to my own heart, what you can efficiently do in polynomial time using a quantum computer. And that's called BQPIT, right? And so, you know, what's understanding?”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“And by the way, it was proven in the 60s that X is larger than p. Okay, so we know that much. We know that there are problems that are solvable.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Into the trunk of your car or something like that. And I ask not just is there a solution, which would be an NP problem, but I ask how many solutions are there? Count the number of valid solutions. That actually gives those problems lie in a complexity class called sharp P or like it looks like hashtag like hashtag P. Got it. Okay, which sits between NP and P-Space There's all the problems that you can do in exponential time. That's called ESP.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“That's right. That's right. But in PSpace, we now have interesting things that were not in NP, like as a famous example, you know, from a given position in chess. Does white or black have the win? Let's say assuming, provided that the game lasts only for a reasonable number of moves or likewise for Go. Okay. And even for the generalizations of these games to arbitrary size boards, because with an 8x8 board, you could say that's just a constant size problem. You just, you know, in principle, you just solve it in O of one time. Right. But so we really mean the generalizations of games to arbitrary size boards here. Or another thing in PSpace would be like, I give you some really hard constraint satisfaction problem. Like, you know, a traveling salesperson or, you know, packing boxes.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Yeah, how do you get more? Yeah, well, okay. I mean, I mean, I mean, just for starters, there is everything that we could do with a conventional computer, with a polynomial amount of memory. But possibly an exponential amount of time because we get to reuse the same memory over and over again. Okay, that is called P-Space. And that's actually a, we think an even larger class than NP. Okay, well, P is contained in NP, which is contained in P-Space. And we think that those containments are strict.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Among all the algorithms, but from a certain theoretical standpoint, that is merely a constant prefector. It's merely a multiplier of your running time. So there are tricks like that one can do to say that in some sense the algorithm would have to be constructive. But in the human sense, it is possible that it's conceivable that one could prove such a thing via a non-constructive method. Is that likely? I don't think so. Not personally.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“So we just ignore those. Okay, but now we just run the first algorithm, then we run the second algorithm, we run the first one a little bit more, then we run the first three algorithms for a while. We run the first four for a while. This is called dovetailing, by the way. This is a known trick in theoretical computer science. But we do it in such a way that whatever is the algorithm out there in our list that solves NP complete, you know, the NP problems efficiently will eventually hit that one, right? And now the key is that whenever we hit that one, by assumption, it has to solve the problem, has to find a solution. And once it claims to find a solution, then we can check that ourselves, right? Because these are problems. Then we can check it. Now, this is utterly impractical, all right? You know, you'd have to do this enormous exhaust.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“But there is such a thing as a non constructive proof that an algorithm exists. You know, this is really only reared its head, I think, a few times in the history of our field, right? But, you know, it is theoretically possible that such a thing could happen. But even here, there are some amusing observations that one could make. So there is this famous observation of Leonid Levin, who was, you know, one of the original discoverers of NP completeness, right? And he said, well, consider the following algorithm, that like, I guarantee we'll solve the NP problems efficiently just as provided that p equals NP. Here is what it does. It just runs, it enumerates every possible algorithm in a gigantic infinite list, right? From alphabetical order, right? And many of them maybe won't even comply.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“It would mean that it exists. Now, in practice, normally the way that we would prove anything like that would be by finding the algorithm.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Okay, you just ask your computer, you know, is there a short proof of the Riemann hypothesis that a machine could, in a language where a machine could verify it, and provided that such a proof exists, then your computer finds it in a short amount of time without having to do a brute force search. Okay, so I mean, I mean, those are the stakes that what we're talking about. But I hope that also helps to give your listeners some intuition of why I and most of my colleagues would put our money on P0 equaling NP.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“If, you know, and now the question is not can you find it? The question has been reduced to does that exist or not? If it does exist, then the answer would be yes, you can find it okay if you had this algorithm in your hands. You could ask your computer, you know, I mean, P versus NP is one of these seven problems that carries this million dollar prize from the Clay Foundation. You know, if you solve it, and others are the Riemann hypothesis, the Punk Array conjecture, which was solved, although the solver turned down the prize, right? And four others. But what I like to say, the way that we can see that P versus NP is the biggest of all of these questions, is that if you had this fast algorithm, then you could solve all seven of them.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Well, okay. I mean, here's an example. I mean, you could, well, okay, just for starters, you could break basically all of the encryption that people use to protect the internet. You could break Bitcoin and every other cryptocurrency or, you know, a mine as much Bitcoin as you wanted, right? You know, become a super duper billionaire, right? And then plot your next move. Right. It's just for starters. That's a good point. Now, your next move might be something like, you know, you now have like a theoretically optimal way to train any neural network, define parameters for any neural network, right? So you could now say like, is there any small neural network that generates the entire content of Wikipedia?”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“You know, ravaged the whole theory of complexity. We would have to rebuild from the ground up. But in practical terms, it might mean very little. If the algorithm was too inefficient to run. If the algorithm could actually be run in practice, like if it had small enough constants or if you could improve it to where it had small enough constants that it was efficient in practice, then that would change the world.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“As well, right? He likes to conjecture that P equals NP, but that the algorithm is so inefficient that it doesn't matter anyway, right? Now, I don't know, I've listened to him say that. I don't know whether he says that just because he has an actual reason for thinking it's true or just because it sounds cool. Yeah. Okay. But, you know, that's a logical possibility, right? That the algorithm could be end to the 10,000 time, or it could even just be n squared time, but with a leading constant. It could be a Google times n squared or something like that. In that case, the fact that p equals np, well, it would”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Well, I do think that it's possible. I mean, in fact, you know, when people really pressed me on my blog for what odds would I put, I put two or three percent odds. Wow, that's pretty good. Yeah, just, well, because, you know, I mean, I mean, you really have to think about like if there were 50 mysteries like P versus NP and if I made a guess about every single one of them, would I expect to be right 50 times? And the truthful answer is no. So, you know, and that's what you really mean in saying that, you know, you have, you know, better than 98% odds for something. Okay. But yeah, you know, I mean, there could certainly be surprises. And look, if P equals NP, well, then there would be the further question of, you know, is the algorithm actually efficient in practice? I mean, Don Canuth, who I know that you've interviewed.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“I mean, no, I mean, it's really just because we are mathematicians or descended from mathematicians, we have to call things conjectures that other people would just call empirical facts or discoveries, right? But one shouldn't read more into that difference in language about the underlying truth.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“That's an easy one. P is not equal to N I like to say that if we were physicists, we would have just declared that to be a law of nature, you know, just like thermodynamics. Giving ourselves Nobel Prizes for its discovery. Yeah, yeah, no. And look, if later it turned out that we were wrong, we just give ourselves more Nobel Prizes.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Any problem wherever there's a solution, there is a short witness that can be easily like a polynomial size witness that can be checked in polynomial time that we call an NP problem. And yeah, so every problem that's in P is also in NP, right? Because, you know, you could always just ignore the witness and just, you know, if the problem is in P, you can just solve it yourself. Okay, but now in some sense, that's the central. Mystery of theoretical computer science is every NP problem in P. So if you can easily check the answer to a computational problem, does that mean that you can also easily find the answer?”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“You the divisors. I said here are three divisors of this number, then it would be very easy for you to ask your computer to just check each one and see if it works. Just divide it in, see if there's any remainder, right? And if they all go in, then you've checked, well, I guess there were, right?”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Then the next super important class is called NP. That stands for non-deterministic polynomial. Does not stand for not polynomial, which is a common confusion. But NP was basically all of the problems where if there is a solution, then it is easy to check the solution if someone shows it to you. So actually a perfect example of a problem in NP is factoring, the one I told you about before. Like if I gave you a number with thousands of digits and I told you that I asked you, does this have at least three non-trivial divisors? That might be a super hard problem to solve, right? It might take you millions of years using any algorithm that's known, at least running on our existing computers. But if I simply show”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Problems that have some polynomial time algorithm. So that includes most of what we do with our computers on a day-to-day basis. All the sorting, basic arithmetic, whatever is going on in your email reader or in angry birds. It's all in P.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source
“Okay, so if your algorithm is linear time, like for adding numbers, that problem is in P. If you have an algorithm that's quadratic time, like the elementary school algorithm for multiplying two numbers, that's also in P, even if it was the size of the input to the tenth power or to the 50th power. Well, that wouldn't be very good in practice. But formally, we would still count that. That would still be in P. Okay, but if your algorithm takes exponential time, meaning like if every time I add one more data point to your input, if the time needed by the algorithm doubles, if you need time like two to the power of the amount of input data, then that we call an exponential time algorithm. That is not polynomial. Okay, so P is all of the problem.”
2020-10-12 · Lex Fridman Podcast · #130 – Scott Aaronson: Computational Complexity and Consciousness · IDENTIFIED FROM THE TRANSCRIPT · source