This is Crazy — Transcript

Full transcript

1. 0:00The exponential time hypothesis is
2. 0:02false. This is completely
3. 0:05insane. OpenAI has done it again. They
4. 0:07are now releasing even more proofs. When
5. 0:10will the proof stop? We are announcing
6. 0:12three new discoveries in mathematics,
7. 0:14computer science, and physics about
8. 0:16harmonic analysis, complexity theory,
9. 0:18and quantum field theory. That's right,
10. 0:21you heard it here. They are releasing a
11. 0:22proof about my boy, computer scientist.
12. 0:25And as somewhat of a computer scientist
13. 0:27myself, I was naturally intrigued. And
14. 0:29learning that the exponential time
15. 0:31hypothesis is false means that we could
16. 0:34fundamentally be entering into an era in
17. 0:37which all modern diseases are solved in
18. 0:40relatively short amount of computation.
19. 0:43And it also means that all encryption is
20. 0:45broken and everything you enjoy is
21. 0:46completely gone and society collapses.
22. 0:48So, we have to talk about this. I'll
23. 0:49help you understand it, okay? As again,
24. 0:52as a computer scientist myself, be glad
25. 0:54to walk you through what is NP-complete,
26. 0:56what this all means, what is the
27. 0:58exponential time hypothesis, and what
28. 1:01does this actually mean? Should you be
29. 1:03worried? Is P equal NP? But before we
30. 1:06do, a quick thank you to the sponsor. I
31. 1:08have to say, one of my favorite parts of
32. 1:10this AI revolution is GrokBot. And that
33. 1:12is because so many little tedious tasks
34. 1:15are now me just going, "Hey, can you
35. 1:16update my calendar with all my kids'
36. 1:18upcoming soccer games for this
37. 1:19tournament?" Or, "Hey, put milk on my
38. 1:21list for things to pick up." And with
39. 1:23the ability to add custom MCPs, you
40. 1:25could actually add any of your
41. 1:26applications and be able to sync with
42. 1:27it. So, GrokBot allows me to effectively
43. 1:30control my life and just take out all
44. 1:32the tedium. Honestly, [laughter] kind of
45. 1:34feels like the promise of AI that we
46. 1:36kept on hearing that it's going to make
47. 1:37our life better. Because this actually
48. 1:39makes life better, and my wife is much
49. 1:42happier now that I'm a little bit more
50. 1:43organized. So, if you like to support
51. 1:45the channel, go check out GrokBot, which
52. 1:46is available on the web, desktop
53. 1:48applications, and on mobile, Android
54. 1:50included. I feel like they were thinking
55. 1:52of me when they made that. I'm very,
56. 1:53very, very happy. All right, so OpenAI
57. 1:56is back at it again. This time, people
58. 1:58are freaking out for a different reason.
59. 2:00It's not for the purity of math that
60. 2:02they're losing everybody on. In fact,
61. 2:03it's for something a little bit
62. 2:05different because if what they have
63. 2:06proved is correct, it is a step towards
64. 2:09P equaling NP. Now, with this
65. 2:11announcement, they actually announced
66. 2:13three big discoveries. The first one for
67. 2:15local smoothing of the Kakeya
68. 2:17conjecture, the third for the existence
69. 2:18of quantum chromodynamics and
70. 2:20completions of the standard model. But
71. 2:22it's the middle one. It's the middle one
72. 2:24we're going to talk about, okay? The
73. 2:25exponential time hypothesis. Now, to
74. 2:28understand the exponential time
75. 2:30hypothesis, you need to understand this
76. 2:33very small Boolean expression right
77. 2:35here. A or B or C. This is called a
78. 2:39three-SAT problem. There's three
79. 2:41variables in a group and we need to see
80. 2:44what values of all the variables need to
81. 2:46be to be able to satisfy this. So, if we
82. 2:48just simply set all of them to false, it
83. 2:50would be false. But if we just set any
84. 2:52one of them to be true, then we have
85. 2:54satisfied that Boolean expression. We
86. 2:56have found something that makes it true.
87. 2:58And in this case, we just set C to true.
88. 3:00But let's make it a little bit harder.
89. 3:01Let's add one more group. So, now we
90. 3:03have two sets of three. This is still a
91. 3:05three-SAT problem. We have A or B or C
92. 3:08and we have not A or D or E. So, now we
93. 3:12have five variables, A through E. So, if
94. 3:15we were to kind of guess, well, what
95. 3:16would satisfy this? We would actually
96. 3:18have to start guessing. Okay, is all of
97. 3:20them false satisfied? No. How about one
98. 3:22of them true? D true? E and D true? How
99. 3:25about C true? Yes, okay, C's true. This
100. 3:27works. Awesome. We now have satisfied
101. 3:30this equation. But notice that it took
102. 3:31quite a few more guesses to get
103. 3:33somewhere. Also, just a side note, the
104. 3:34fact that this actually is the same It's
105. 3:37the same thing that made them both true.
106. 3:39That's just anomaly, just okay, don't
107. 3:41think about it too hard. All right, so
108. 3:42let's add actually a third one in here.
109. 3:43Notice that we have not C in the third
110. 3:45one, F and G. So, that that puts our
111. 3:47total variables all the way up to G or
112. 3:50seven. So, now when we're checking,
113. 3:52notice that this takes a lot longer. We
114. 3:53have a lot more guesses. Like this would
115. 3:55take us a while to figure out. If you
116. 3:56were doing this by hand, you would have
117. 3:58to do a bit of guessing. Lo and behold,
118. 4:01we got it. We were able to get the
119. 4:03answer after so many guesses, but you
120. 4:05can see something here. Every time we
121. 4:07add a new group, and more specifically,
122. 4:09every time we add a new variable, this
123. 4:11requires a much larger amount of
124. 4:14checking. Now, this is kind of like the
125. 4:16fundamental premise of the exponential
126. 4:18time hypothesis. This hypothesis is
127. 4:21super important because if it is true,
128. 4:24then P does not equal NP. But, right
129. 4:27now, it hasn't been proven to be
130. 4:29actually true. It's only a hypothesis,
131. 4:31and the basic of the hypothesis is that
132. 4:34the growth of the three SAT problem is
133. 4:37effectively bounded exponentially, like
134. 4:39two to the end. Now, there are some
135. 4:41improvements on the algorithms, and
136. 4:42people have been able to kind of reduce
137. 4:44that base down to 1.3 with clever
138. 4:46programming tricks, but that still is
139. 4:481.3 to the end. To put this into
140. 4:51perspective, I'm going to give a very
141. 4:52special number. Just go with it for a
142. 4:54second. 1.3 to the 2,500. This right
143. 4:57here is more atoms than the known
144. 5:00universe. So, you can see that even with
145. 5:03that much smaller base, when you get to
146. 5:05so many of these, it becomes impossible
147. 5:08to actually compute. Like, we don't have
148. 5:10the computation ever to be able to solve
149. 5:12this. But, what OpenAI just did is they
150. 5:15found an equation that they were able to
151. 5:17solve that looks like this: two to the
152. 5:19end divided by the squirt of the log of
153. 5:23n.
154. 5:25And this takes it from being exponential
155. 5:28to being sub-exponential,
156. 5:30which is exactly what Eve said, "Nope.
157. 5:32That cannot happen. I'll put MY FOOT ON
158. 5:34THE GROUND. WE WILL NOT HAVE
159. 5:37non-exponentials here. No, we'll we
160. 5:39actually have sub-exponential." Now,
161. 5:40this is not polynomial time. This is
162. 5:42still exponential time, but it's
163. 5:44sub-exponential. Because this does grow
164. 5:47with the growth of n, which makes n
165. 5:49smaller. So, the growth is just not
166. 5:52quite the same. If you remember my last
167. 5:53equation, that 1.3 to the 2,500, you can
168. 5:55see right here, that has greatly reduced
169. 5:57it. Now, this is still completely not
170. 5:59even computable. That number is just
171. 6:01gigantic. We're not going to be able to
172. 6:03solve that in my lifetime, but as you
173. 6:05can see it's significantly reduced. And
174. 6:07this means is there a path to continuing
175. 6:10to reduce this? Are we just starting the
176. 6:13walking of reducing this? Now, this may
177. 6:15sound a little bit familiar because if
178. 6:16you just remember a few weeks ago on
179. 6:19October 6th when OpenAI dropped like 372
180. 6:23different proofs or was it I can't
181. 6:26remember what it was. Doesn't really
182. 6:27matter. It was a lot of proofs. One of
183. 6:29them was about integer multiplication.
184. 6:32The integer multiplication started off
185. 6:34as being this like barely in just the
186. 6:36tiniest improvement of all time. And
187. 6:39then over the course of the next couple
188. 6:41weeks, you started seeing improvement
189. 6:43and improvement and improvement. So, is
190. 6:45this going to be another one of those
191. 6:46cases where it starts off with just
192. 6:48barely a little bit of an improvement
193. 6:50that just leads to a deluge of huge
194. 6:53improvements on this running time? Are
195. 6:55we going to see something like P does
196. 6:56not equal NP? Now, you're probably
197. 6:58asking, "I don't know what P equal does
198. 7:01not equal NP even means." What is the
199. 7:03implication? This is where all the scary
200. 7:05stuff actually happens because if this
201. 7:07starts to improve a whole bunch and we
202. 7:09open up new doors and we eventually get
203. 7:11this all the way down into polynomial
204. 7:13time, this will just upend society. Yes,
205. 7:17P equals NP will make things kind of
206. 7:19crazy for us. Okay, so we have to talk
207. 7:21about P equals NP because this is the
208. 7:24big question because if P equals NP, we
209. 7:26are all screwed and we are also in
210. 7:29in a super great world where we could
211. 7:31cure cancer. It's the craziest world we
212. 7:32could ever possibly live in. And this is
213. 7:34why. There exists a set of problems
214. 7:36called NP problems, non-deterministic
215. 7:39polynomial problems. These problems have
216. 7:41a very special condition on them. They
217. 7:43can be verified in polynomial time. This
218. 7:46is really important. So, when we go back
219. 7:48to this, I can look at this one right
220. 7:50here and go like this, "Okay, that one's
221. 7:51true. That one's true because not zero.
222. 7:53And that one's true." Boom. I just
223. 7:55verified with my eyeballs a problem that
224. 7:57is super hard, that is exponentially
225. 7:59difficult to solve for, but I can verify
226. 8:02it in linear time. It's super easy to
227. 8:04see if something's right, super hard to
228. 8:06determine the problem. Inside of NP,
229. 8:08there's a set of problems called P. And
230. 8:11now, this is the big question. Is all
231. 8:13the problems in NP P, or is just some of
232. 8:16them? P means that they are solvable in
233. 8:18polynomial time. See, then there's one
234. 8:20other group of problems we'd like to
235. 8:22call NP-hard. Now, this is kind of a
236. 8:24funny one. It has a fairly funny name to
237. 8:26it because you're like, "Oh, well, why
238. 8:27aren't all the problems inside of NP?"
239. 8:28It's called NP-hard. Well, what they
240. 8:30mean is that they're at least as hard as
241. 8:33every other problem inside of NP. And
242. 8:35so, this little intersection right here
243. 8:36is a very special class of problems we
244. 8:38like to refer to as NP-complete.
245. 8:41NP-complete problems are NP-hard
246. 8:43problems that are verifiable in
247. 8:45polynomial time. This problem is
248. 8:48NP-complete. Now, NP-complete has this
249. 8:50really special property, which every
250. 8:51problem that is NP-complete, you can
251. 8:54represent by any other problem that's
252. 8:56NP-complete. Meaning that the traveling
253. 8:57salesman can actually be represented as
254. 9:00a three-SAT problem. That is why I
255. 9:02showed you this little formula over
256. 9:04here, because 2,500 is the size of the
257. 9:07United States being represented as a
258. 9:09three-SAT formula solving the traveling
259. 9:11salesman, which means it takes forever
260. 9:13to solve. We can't solve this even with
261. 9:15the best stuff The best computers in the
262. 9:17universe can't solve that problem right
263. 9:18now. But, here's the thing. With that
264. 9:19paper showing that exponential time
265. 9:21hypothesis is in fact false, that we are
266. 9:25sub-exponential,
267. 9:27there's a chance that we could keep on
268. 9:28figuring out how to reduce it in the
269. 9:30polynomial time. And that's where things
270. 9:33get crazy. And the reason why is that
271. 9:35once one of these problems become
272. 9:37polynomial time, all of these problems
273. 9:40become polynomial time by the sheer
274. 9:42nature that they are the hardest of all
275. 9:44the problems within NP. Now, where this
276. 9:46gets really, really bad is think of RSA.
277. 9:49RSA, which of course is like how you do
278. 9:51public key encryption. There's like many
279. 9:53versions of this, and this is not the
280. 9:55complete picture, but just go with me
281. 9:57here. Effectively, there's two prime
282. 9:59numbers that are multiplied together,
283. 10:01and then you get this public key that
284. 10:03anybody can look at, and it's completely
285. 10:05fine because they don't know how to get
286. 10:06these private keys from this public one.
287. 10:09Yes, I know there's an inverted matrix
288. 10:10involved in all of this. We're not going
289. 10:12to talk about it. Just don't worry about
290. 10:13that, okay? Just keep it simple. So,
291. 10:15that means these private keys to be able
292. 10:17to find those, you have to do something
293. 10:19called integer factorization. And that
294. 10:22turns out to be a really hard problem.
295. 10:24Not an NP-hard problem, but a very hard
296. 10:26problem inside of MP because we can
297. 10:27validate that in polynomial time, but we
298. 10:30cannot solve for it in polynomial time.
299. 10:33And since exponential time hypothesis is
300. 10:35now false and we are now
301. 10:36sub-exponential, if this does improve
302. 10:38and go to polynomial, that means we can
303. 10:40crack RSA in polynomial time, which
304. 10:42means powerful computers would be able
305. 10:44to break encryption across the internet.
306. 10:46This also goes for like SHA-256. This
307. 10:49also goes for HMAC. This goes for
308. 10:50pseudo-random number generators. It goes
309. 10:52for blockchain, which awesome, love to
310. 10:54see that last one get taken down. But,
311. 10:57nonetheless, everything would kind of
312. 10:59fall apart. But, there's also protein
313. 11:01folding. Turns out protein folding is in
314. 11:03fact going to be an NP-complete problem.
315. 11:05So, if we could change that, we could
316. 11:06potentially do research what would take
317. 11:09decades or hundreds of years, you could
318. 11:11potentially do in like a year. You would
319. 11:13even be able to solve Sudokus in
320. 11:15polynomial time. Now, that would be a
321. 11:17crazy world, right? I mean, solving
322. 11:19Sudokus? Okay, that's getting a little
323. 11:21too fanciful. The name
324. 11:24is the NP engine.