1 00:00:00,000 --> 00:00:02,899 So if you wanted to use a brute force algorithm 2 00:00:02,899 --> 00:00:05,599 to securely route just a single encrypted message 3 00:00:05,599 --> 00:00:07,980 across the internet, checking every possible 4 00:00:07,980 --> 00:00:10,099 path and combination to make sure it was optimal 5 00:00:10,099 --> 00:00:13,019 and secure, your laptop would literally need 6 00:00:13,019 --> 00:00:15,320 to run for longer than the universe has existed. 7 00:00:15,820 --> 00:00:17,920 Right, which is obviously not very practical. 8 00:00:18,219 --> 00:00:21,620 No, not at all. But thanks to a few clever mathematical 9 00:00:21,620 --> 00:00:23,620 tricks that we actually learned in primary school, 10 00:00:23,800 --> 00:00:25,800 your phone handles that routing and encryption 11 00:00:25,800 --> 00:00:29,160 in a fraction of a millisecond. Exactly. Yeah. 12 00:00:29,289 --> 00:00:31,629 So today, we are opening the textbook you sent 13 00:00:31,629 --> 00:00:34,509 us to find out exactly where that boundary lies 14 00:00:34,509 --> 00:00:37,929 between the mathematically easy and the fundamentally 15 00:00:37,929 --> 00:00:40,890 impossible. We're doing a deep dive into Thomas 16 00:00:40,890 --> 00:00:43,770 Watson's textbook, Complexity in Computer Science. 17 00:00:44,450 --> 00:00:47,710 It's honestly a remarkable text. And Watson actually 18 00:00:47,710 --> 00:00:49,609 dedicates it to the memory of his father, Andrew 19 00:00:49,609 --> 00:00:53,009 Watson, which I think immediately grounds this 20 00:00:53,009 --> 00:00:55,189 what is otherwise a highly abstract theoretical 21 00:00:55,189 --> 00:00:58,210 subject in a deeply personal reality. Yeah, I 22 00:00:58,210 --> 00:01:01,500 love to that part. It's necessary, I think, because 23 00:01:01,500 --> 00:01:03,539 the whole philosophy of the book is tackling 24 00:01:03,539 --> 00:01:06,840 what musicians call playing easy music and hard 25 00:01:06,840 --> 00:01:09,420 keys. Easy music and hard keys. I like that. 26 00:01:09,799 --> 00:01:12,579 The mathematics of computer science is a notoriously 27 00:01:12,579 --> 00:01:15,840 hard key. I mean, the rigor demands absolute 28 00:01:15,840 --> 00:01:18,819 precision. But Watson's mission is to provide 29 00:01:18,819 --> 00:01:22,140 the easy music, making those mathematically demanding 30 00:01:22,140 --> 00:01:24,939 concepts accessible without ever sacrificing 31 00:01:24,939 --> 00:01:28,250 the strict boundaries of the field. He uses this 32 00:01:28,250 --> 00:01:30,549 really beautiful analogy right in the prologue 33 00:01:30,549 --> 00:01:32,969 comparing the study of computational complexity 34 00:01:32,969 --> 00:01:35,849 to exploring a huge mansion, you know with grand 35 00:01:35,849 --> 00:01:39,090 architecture or secret passages and Surprises 36 00:01:39,090 --> 00:01:41,829 behind many doors. It's a great way to frame 37 00:01:41,829 --> 00:01:44,519 it We are definitely going to be opening a lot 38 00:01:44,519 --> 00:01:47,700 of those doors for you today But okay, let's 39 00:01:47,700 --> 00:01:50,099 unpack this right from the start I have to push 40 00:01:50,099 --> 00:01:52,040 back on the fundamental premise before we even 41 00:01:52,040 --> 00:01:54,900 cross the threshold go for it Why do we even 42 00:01:54,900 --> 00:01:57,319 need an entire branch of mathematics dedicated 43 00:01:57,319 --> 00:02:00,000 to what computers cannot do? I mean, if an engineer 44 00:02:00,000 --> 00:02:02,000 encounters a slow program, they don't invent 45 00:02:02,000 --> 00:02:04,420 a mathematical theorem to prove it's slow, right? 46 00:02:04,439 --> 00:02:06,620 They just add more RAM, build a faster processor, 47 00:02:07,099 --> 00:02:09,300 or, I don't know, design a better quantum architecture. 48 00:02:09,800 --> 00:02:12,539 Well, sure, that engineer's instinct is supernatural, 49 00:02:12,599 --> 00:02:14,780 but it completely misses the scale of the problems 50 00:02:14,780 --> 00:02:17,539 we're actually dealing with here. Complexity 51 00:02:17,539 --> 00:02:21,629 theory transcends hardware. How so? We are talking 52 00:02:21,629 --> 00:02:24,389 about the mathematical growth rates of problems. 53 00:02:25,050 --> 00:02:26,889 If the number of steps required to solve a problem 54 00:02:26,889 --> 00:02:29,389 doubles every single time you add just a tiny 55 00:02:29,389 --> 00:02:31,810 piece of data to the input, you hit a physical 56 00:02:31,810 --> 00:02:34,449 wall. Right. Even if every atom in the known 57 00:02:34,449 --> 00:02:37,330 universe were a processor operating at the speed 58 00:02:37,330 --> 00:02:40,330 of light, you still wouldn't have enough computational 59 00:02:40,330 --> 00:02:42,430 power to solve certain problems if the input 60 00:02:42,430 --> 00:02:45,889 is just, say, a few hundred bits long. Wow. Okay, 61 00:02:45,889 --> 00:02:49,150 so it's just completely out of the realm of physical 62 00:02:49,150 --> 00:02:53,300 reality. Exactly. Complexity theory exists to 63 00:02:53,300 --> 00:02:56,280 save engineers from wasting decades trying to 64 00:02:56,280 --> 00:02:58,240 write an efficient algorithm for a problem that 65 00:02:58,240 --> 00:03:00,900 mathematically just cannot have one. So it's 66 00:03:00,900 --> 00:03:03,400 about adjusting our expectations and avoiding 67 00:03:03,400 --> 00:03:06,599 totally futile attempts. But if we are going 68 00:03:06,599 --> 00:03:09,560 to make a grand universal claim that no computer 69 00:03:09,560 --> 00:03:12,020 in existence can solve a specific problem efficiently, 70 00:03:12,599 --> 00:03:15,120 we better be absolutely sure we know what a computer 71 00:03:15,120 --> 00:03:19,219 actually is, right? Yes, exactly. We need a rigorous 72 00:03:19,219 --> 00:03:21,719 mathematical model. And when you take a standard 73 00:03:21,719 --> 00:03:24,300 theory class, you usually get handed the Turing 74 00:03:24,300 --> 00:03:27,199 machine. You know, an infinitely long tape, a 75 00:03:27,199 --> 00:03:28,960 little read -write head moving back and forth 76 00:03:28,960 --> 00:03:31,460 one square at a time. Which is very austere. 77 00:03:31,879 --> 00:03:34,360 Very simple. Yeah, but Watson kind of pushes 78 00:03:34,360 --> 00:03:37,039 us away from it, doesn't he? He does. And the 79 00:03:37,039 --> 00:03:40,900 reasoning is rooted in practical intuition. What's 80 00:03:40,900 --> 00:03:42,979 fascinating here is that while the Turing machine 81 00:03:42,979 --> 00:03:46,080 is historically vital, it introduces massive 82 00:03:46,080 --> 00:03:48,979 artificial friction when you try to measure realistic 83 00:03:48,979 --> 00:03:51,360 efficiency. Like it makes things look slower 84 00:03:51,360 --> 00:03:54,800 than they are? Precisely. Imagine writing a program 85 00:03:54,800 --> 00:03:57,939 to do basic addition on a Turing tape. The machine 86 00:03:57,939 --> 00:04:00,939 has to tediously crawl back and forth across 87 00:04:00,939 --> 00:04:04,139 the tape, moving one square at a time just to 88 00:04:04,139 --> 00:04:06,900 carry a one to the next column. Oh, right, because 89 00:04:06,900 --> 00:04:09,400 it can't just jump to the tens column. Exactly. 90 00:04:10,530 --> 00:04:12,789 Mathematically, it adds what we call an O of 91 00:04:12,789 --> 00:04:15,889 N log N overhead just to do basic data manipulation. 92 00:04:16,490 --> 00:04:18,550 It makes simple algorithms look mathematically 93 00:04:18,550 --> 00:04:20,910 slower than they actually would be on the laptop 94 00:04:20,910 --> 00:04:23,230 sitting right in front of you. So it basically 95 00:04:23,230 --> 00:04:25,810 punishes algorithms for the physical layout of 96 00:04:25,810 --> 00:04:28,290 a one -dimensional tape. Watson's alternative 97 00:04:28,290 --> 00:04:30,829 to this is the Word RAM model, right? Yeah, the 98 00:04:30,829 --> 00:04:33,250 Word RAM model. It behaves much more like an 99 00:04:33,250 --> 00:04:36,370 idealized assembly language. It has memory made 100 00:04:36,370 --> 00:04:40,069 up of words. chunks of bits, and it has registers. 101 00:04:41,230 --> 00:04:43,410 Okay. Crucially, it can jump around to different 102 00:04:43,410 --> 00:04:46,069 memory addresses in a single step, mimicking 103 00:04:46,069 --> 00:04:49,230 the random access memory in modern devices. It 104 00:04:49,230 --> 00:04:52,389 has basic instructions built in, like add, subtract, 105 00:04:52,829 --> 00:04:56,610 load, store. So it's way closer to how an actual 106 00:04:56,610 --> 00:04:59,750 computer works today. Much closer. When you analyze 107 00:04:59,750 --> 00:05:02,389 an algorithm in the Word RAM model, the time 108 00:05:02,389 --> 00:05:04,990 it takes, which we measure in elementary steps, 109 00:05:05,470 --> 00:05:08,089 and the space it uses, measured in working memory. 110 00:05:08,529 --> 00:05:11,050 They align much more closely with what a software 111 00:05:11,050 --> 00:05:13,829 developer actually experiences. Wait, hold on. 112 00:05:14,230 --> 00:05:16,649 I see a potential flaw with the word RAM model. 113 00:05:16,910 --> 00:05:19,689 Oh, what's that? If the computer has to jump 114 00:05:19,689 --> 00:05:22,250 to any memory address in a single step, it needs 115 00:05:22,250 --> 00:05:24,889 to hold that entire memory address in a single 116 00:05:24,889 --> 00:05:28,529 word or register, right? Right. So if your input 117 00:05:28,529 --> 00:05:31,569 data gets massive, the number of memory addresses 118 00:05:31,569 --> 00:05:34,290 gets massive too. Doesn't that mean the size 119 00:05:34,290 --> 00:05:37,459 of the word itself has to constantly flex and 120 00:05:37,459 --> 00:05:40,720 grow depending on how big the input is, that 121 00:05:40,720 --> 00:05:45,579 seems like baggage. That is a really sharp observation. 122 00:05:46,100 --> 00:05:48,459 You're totally right. The word size in the word 123 00:05:48,459 --> 00:05:51,459 RAM model must grow logarithmically with the 124 00:05:51,459 --> 00:05:54,660 input size. Ah, OK. If your input size, let's 125 00:05:54,660 --> 00:05:57,560 call it n, is huge, you need an address that 126 00:05:57,560 --> 00:06:00,480 is log n bits long just to point to the end of 127 00:06:00,480 --> 00:06:04,100 it. This does introduce some annoying theoretical 128 00:06:04,100 --> 00:06:07,149 baggage. Like, when you combine two algorithms 129 00:06:07,149 --> 00:06:09,149 that expect different word sizes, you have to 130 00:06:09,149 --> 00:06:11,170 do conversion math. Which the Turing machine 131 00:06:11,170 --> 00:06:13,170 ignores completely. Right, because its tape head 132 00:06:13,170 --> 00:06:15,569 just moves blindly one square at a time. It doesn't 133 00:06:15,569 --> 00:06:17,790 need to hold a massive address in its head. But, 134 00:06:17,810 --> 00:06:20,350 you know, that baggage perfectly mirrors real 135 00:06:20,350 --> 00:06:22,310 -world architectural constraints. I mean, this 136 00:06:22,310 --> 00:06:24,769 is exactly why the computing industry had to 137 00:06:24,769 --> 00:06:27,329 abandon 32 -bit operating systems and move to 138 00:06:27,329 --> 00:06:30,149 64 -bit. Exactly. A 32 -bit architecture could 139 00:06:30,149 --> 00:06:33,149 only address about four gigabytes of RAM. Right. 140 00:06:33,149 --> 00:06:35,149 And when databases and games got larger than 141 00:06:35,149 --> 00:06:37,990 4 gigs, the physical processor literally ran 142 00:06:37,990 --> 00:06:40,410 out of numbers to label the memory addresses. 143 00:06:41,410 --> 00:06:44,269 So Word RAM sacrifices a tiny bit of theoretical 144 00:06:44,269 --> 00:06:47,089 purity to accurately capture how our silicon 145 00:06:47,089 --> 00:06:49,750 actually functions. It enters the theory to reality. 146 00:06:50,149 --> 00:06:52,689 And with that realistic model, we can start categorizing 147 00:06:52,689 --> 00:06:55,050 algorithms by their time efficiency using big 148 00:06:55,050 --> 00:06:58,290 O notation. Which abstracts away the exact megahertz 149 00:06:58,290 --> 00:07:00,410 speed of the processor, right? Yeah, we focus 150 00:07:00,410 --> 00:07:03,170 purely on the scaling curve. This leads us to 151 00:07:03,170 --> 00:07:05,269 the most critical distinction in the whole field. 152 00:07:05,910 --> 00:07:09,129 Polynomial time, known as the class P, versus 153 00:07:09,129 --> 00:07:13,110 exponential time, known as the class EXP. OK, 154 00:07:13,110 --> 00:07:15,009 so the conventional wisdom is that polynomial 155 00:07:15,009 --> 00:07:18,930 time is efficient and exponential time is inefficient. 156 00:07:19,350 --> 00:07:22,149 Like if your algorithm runs in time bounded by 157 00:07:22,149 --> 00:07:24,350 n to the power of some constant, like n squared 158 00:07:24,350 --> 00:07:27,870 or n cubed, it's in P. Correct. But I want to 159 00:07:27,870 --> 00:07:29,370 clarify something important for the listener 160 00:07:29,370 --> 00:07:32,100 here. This is a strict theoretical convention. 161 00:07:32,800 --> 00:07:35,740 If an algorithm takes n to the power of 100 steps, 162 00:07:35,939 --> 00:07:38,920 it is mathematically in p. But for an input of 163 00:07:38,920 --> 00:07:42,300 just two bits, 2 to the power of 100 steps is 164 00:07:42,300 --> 00:07:44,620 already completely impractical in the real world. 165 00:07:44,980 --> 00:07:47,019 It is vital to maintain that distinction, yes. 166 00:07:47,740 --> 00:07:50,959 P does not guarantee real -world speed. But theorists 167 00:07:50,959 --> 00:07:53,319 focus on polynomial time because polynomials 168 00:07:53,319 --> 00:07:57,060 scale predictably. Right. As n grows, the growth 169 00:07:57,060 --> 00:07:59,699 curve of a polynomial remains relatively tame 170 00:07:59,699 --> 00:08:02,980 compared to the alternative. Exponential time, 171 00:08:03,000 --> 00:08:05,600 where the algorithm takes 2 to the power of n 172 00:08:05,600 --> 00:08:09,639 steps, grows so explosively, it basically defies 173 00:08:09,639 --> 00:08:12,519 human comprehension. Yeah. Watson points out 174 00:08:12,519 --> 00:08:16,220 that if n is just 300, and a 300 -bit input is 175 00:08:16,220 --> 00:08:18,899 less data than a single text message, 2 to the 176 00:08:18,899 --> 00:08:22,319 300 is greater than the number of atoms in the 177 00:08:22,319 --> 00:08:24,939 observable universe. That puts the boundary into 178 00:08:24,939 --> 00:08:27,980 really stark perspective. However, we must introduce 179 00:08:27,980 --> 00:08:30,740 a strict nuance here regarding the class EXP. 180 00:08:31,040 --> 00:08:33,779 Okay, what's the nuance? EXP is an upper bound 181 00:08:33,779 --> 00:08:36,820 class. When we say a problem belongs to EXP, 182 00:08:37,179 --> 00:08:39,419 we are absolutely not claiming that every single 183 00:08:39,419 --> 00:08:41,600 instance of that problem requires exponential 184 00:08:41,600 --> 00:08:44,299 time. Wait, really? I think a lot of people misunderstand 185 00:08:44,299 --> 00:08:46,799 that. They do. We are only guaranteeing that 186 00:08:46,799 --> 00:08:49,299 it can be solved in at most exponential time. 187 00:08:49,519 --> 00:08:52,529 It is a worst case ceiling. Some specific inputs 188 00:08:52,529 --> 00:08:55,370 might actually be solved instantly. Ah, got it. 189 00:08:55,830 --> 00:08:58,049 So, to really drive home the difference between 190 00:08:58,049 --> 00:09:00,169 polynomial and exponential growth for our listeners, 191 00:09:00,450 --> 00:09:02,649 let's look at how computers multiply numbers. 192 00:09:03,210 --> 00:09:05,649 If you take two numbers, x and y, and multiply 193 00:09:05,649 --> 00:09:07,750 them using a brute force approach, you just add 194 00:09:07,750 --> 00:09:11,169 x to a running total y times. Right. Let's map 195 00:09:11,169 --> 00:09:12,950 out the scaling for that brute force addition. 196 00:09:13,669 --> 00:09:16,750 The input size, n, is the number of bits required 197 00:09:16,750 --> 00:09:20,259 to represent x and y. A binary number represented 198 00:09:20,259 --> 00:09:23,220 by n bits can have a numeric value as large as 199 00:09:23,220 --> 00:09:27,000 2 to the power of n. So if your loop runs y times, 200 00:09:27,700 --> 00:09:29,879 it could run 2 to the n times in the worst case. 201 00:09:30,379 --> 00:09:33,019 Which is an exponential time algorithm. Exactly. 202 00:09:33,360 --> 00:09:35,960 If you use that method to multiply two 300 -bit 203 00:09:35,960 --> 00:09:38,559 numbers, the universe would suffer heat death 204 00:09:38,559 --> 00:09:40,440 before your computer finished. Which would break 205 00:09:40,440 --> 00:09:43,059 the modern internet entirely, right? Since RSA 206 00:09:43,059 --> 00:09:45,639 cryptography relies on constantly multiplying 207 00:09:45,639 --> 00:09:48,519 prime numbers that are thousands of bits long. 208 00:09:48,720 --> 00:09:51,240 It would completely break it. Thankfully, we 209 00:09:51,240 --> 00:09:52,980 adopt the primary school multiplication method 210 00:09:52,980 --> 00:09:56,120 for base to binary numbers. We use bit shifts. 211 00:09:56,620 --> 00:09:58,980 How does that work in this model? The algorithm 212 00:09:58,980 --> 00:10:01,940 looks at each bit of y. If the bit is a one, 213 00:10:02,179 --> 00:10:04,559 it shifts x by the appropriate amount and adds 214 00:10:04,559 --> 00:10:07,919 it. Since y is n bits long, the main loop only 215 00:10:07,919 --> 00:10:10,559 runs n times. Oh, wow. And the inner addition 216 00:10:10,559 --> 00:10:13,639 also runs about n times. So the total operation 217 00:10:13,639 --> 00:10:18,200 scale with n times n, or O of n squared, it is 218 00:10:18,200 --> 00:10:21,379 safely in polynomial time. We went from an algorithm 219 00:10:21,379 --> 00:10:24,120 taking longer than cosmic history to one that 220 00:10:24,120 --> 00:10:27,000 executes in microseconds, simply by exploiting 221 00:10:27,000 --> 00:10:29,279 mathematical structure. That is just incredible. 222 00:10:30,039 --> 00:10:32,539 And this brings up an advanced concept that Watson 223 00:10:32,539 --> 00:10:35,940 weaves into the text. We have P. And we have 224 00:10:35,940 --> 00:10:39,480 EXP, but the boundary isn't always a clean, sudden 225 00:10:39,480 --> 00:10:42,480 cliff. There are layers to exponential time. 226 00:10:42,919 --> 00:10:45,879 You sent us some notes on Seth, the strong exponential 227 00:10:45,879 --> 00:10:48,860 time hypothesis? Yeah, SETH is a fascinating 228 00:10:48,860 --> 00:10:51,000 conjecture that refines our understanding of 229 00:10:51,000 --> 00:10:53,279 these worst -case upper bounds. Okay, lay it 230 00:10:53,279 --> 00:10:56,120 out for us. Consider the Boolean Satisfiability 231 00:10:56,120 --> 00:10:59,519 Problem, or SAT. We know we can solve it by checking 232 00:10:59,519 --> 00:11:01,580 every possible assignment of true and false to 233 00:11:01,580 --> 00:11:03,419 the variables, which takes roughly two to the 234 00:11:03,419 --> 00:11:07,429 end time. standard brute force. Right. SETH essentially 235 00:11:07,429 --> 00:11:10,330 posits that for general SAT formulas, you cannot 236 00:11:10,330 --> 00:11:13,070 find a uniform algorithm that significantly improves 237 00:11:13,070 --> 00:11:15,750 the base of that exponent across the board. So 238 00:11:15,750 --> 00:11:19,590 no magic shortcuts? Exactly. It hypothesizes 239 00:11:19,590 --> 00:11:22,049 that as the clauses in your formula get wider 240 00:11:22,049 --> 00:11:24,809 and more complex, the time required strictly 241 00:11:24,809 --> 00:11:27,809 approaches 2 to the n. There is no magic algorithm 242 00:11:27,809 --> 00:11:30,169 hiding out there that can solve all SAT variants 243 00:11:30,169 --> 00:11:34,009 in, say, 1 .5 to the n time. So it sets a concrete 244 00:11:34,009 --> 00:11:36,409 floor on the exponential growth. But there is 245 00:11:36,409 --> 00:11:38,450 a flip side to this when dealing with intractable 246 00:11:38,450 --> 00:11:42,610 problems. Parameterized complexity in FPT, fixed 247 00:11:42,610 --> 00:11:45,070 parameter tractability. Instead of just throwing 248 00:11:45,070 --> 00:11:47,289 our hands up and saying a problem is exponential 249 00:11:47,289 --> 00:11:49,830 and impossible, we isolate why it's blowing up. 250 00:11:50,009 --> 00:11:53,490 Yes. Parameterized complexity is a highly pragmatic 251 00:11:53,490 --> 00:11:56,009 tool. Instead of just looking at the total input 252 00:11:56,009 --> 00:11:59,429 size n, we identify a specific parameter within 253 00:11:59,429 --> 00:12:02,720 the input. Let's call it k. OK. A problem is 254 00:12:02,720 --> 00:12:06,200 in FPT, if it can be solved in time f of k times 255 00:12:06,200 --> 00:12:09,879 n to the power of c, where c is a constant that 256 00:12:09,879 --> 00:12:12,899 is completely independent of k. Right, so the 257 00:12:12,899 --> 00:12:15,100 exponential explosion is entirely contained within 258 00:12:15,100 --> 00:12:18,860 that function f of k. The n part remains a nice, 259 00:12:19,080 --> 00:12:21,480 predictable polynomial. A classic example here 260 00:12:21,480 --> 00:12:24,480 is the vertex cover problem. You have a massive 261 00:12:24,480 --> 00:12:27,200 network graph of size n, and you want to find 262 00:12:27,200 --> 00:12:30,720 a small set of k central nodes that touch every 263 00:12:30,720 --> 00:12:32,980 single edge in the network. And finding a verdict's 264 00:12:32,980 --> 00:12:35,580 cover is notoriously hard overall, right? It 265 00:12:35,580 --> 00:12:38,740 is. But it turns out we have an FPT algorithm 266 00:12:38,740 --> 00:12:41,899 for it. It runs in time roughly 2 to the power 267 00:12:41,899 --> 00:12:45,360 of k times n. If you are only looking for a small 268 00:12:45,360 --> 00:12:50,700 cover, say k is 10, 2 to the 10 is just 1 ,024. 269 00:12:51,659 --> 00:12:53,919 Multiply that by your network size n, and the 270 00:12:53,919 --> 00:12:56,139 problem is completely manageable, even if n is 271 00:12:56,139 --> 00:12:58,980 a million. That is a massive lifeline for engineers. 272 00:12:59,159 --> 00:13:01,230 It really is. But it doesn't work for everything, 273 00:13:01,389 --> 00:13:04,169 does it? I mean, finding an independent set of 274 00:13:04,169 --> 00:13:06,870 size k, which is finding nodes that don't touch 275 00:13:06,870 --> 00:13:09,690 each other at all, that looks structurally similar, 276 00:13:09,690 --> 00:13:13,210 but it's classified as W1 complete. Exactly. 277 00:13:13,590 --> 00:13:16,769 It is not known to admit an FPT algorithm. The 278 00:13:16,769 --> 00:13:20,070 exponent on n grows as k grows, which just drags 279 00:13:20,070 --> 00:13:22,269 the whole thing down into the mud. You can't 280 00:13:22,269 --> 00:13:25,309 just contain the explosion in k. By contrast, 281 00:13:25,629 --> 00:13:28,090 an algorithm running in n to the power of k is 282 00:13:28,090 --> 00:13:32,120 in the class XP. which is distinctly slower than 283 00:13:32,120 --> 00:13:34,639 FPT because the polynomial degree itself keeps 284 00:13:34,639 --> 00:13:36,940 growing. It demonstrates that even within the 285 00:13:36,940 --> 00:13:39,539 realm of intractable problems, there are strict 286 00:13:39,539 --> 00:13:42,460 mathematical hierarchies of difficulty. Now, 287 00:13:42,460 --> 00:13:45,220 time is just one resource. We also have to consider 288 00:13:45,220 --> 00:13:48,220 space, the working memory an algorithm requires. 289 00:13:48,440 --> 00:13:51,120 Space is just as crucial. The textbook outlines 290 00:13:51,120 --> 00:13:53,440 a problem called directed reachability to illustrate 291 00:13:53,440 --> 00:13:56,919 space. You have a map with a starting city S 292 00:13:56,919 --> 00:14:00,320 and a target city T. You just want to know, is 293 00:14:00,320 --> 00:14:03,340 there a valid sequence of roads from S to T? 294 00:14:04,059 --> 00:14:06,580 And a brute force approach where you try every 295 00:14:06,580 --> 00:14:11,100 single permutation of roads scales. Factorally, 296 00:14:11,179 --> 00:14:13,820 it's impossible. Right. So what do we do instead? 297 00:14:14,360 --> 00:14:18,080 We use breadth first search or BFS. It explores 298 00:14:18,080 --> 00:14:20,980 outward like a ripple in a pond. But to implement 299 00:14:20,980 --> 00:14:24,039 that ripple, the algorithm needs a cue to remember 300 00:14:24,039 --> 00:14:26,740 which cities it has discovered but hasn't yet 301 00:14:26,740 --> 00:14:30,120 visited. And tracking this requires space. Exactly. 302 00:14:30,279 --> 00:14:33,379 If the map has n cities, the queue might need 303 00:14:33,379 --> 00:14:36,419 to store all n cities in the worst case. So the 304 00:14:36,419 --> 00:14:40,600 space complexity scales linearly O of n. So time 305 00:14:40,600 --> 00:14:43,000 and space are really the two fundamental currencies 306 00:14:43,000 --> 00:14:46,200 of computation. And the grand map of complexity 307 00:14:46,200 --> 00:14:48,940 classes is basically built by examining how these 308 00:14:48,940 --> 00:14:51,399 two currencies constrain each other. That's a 309 00:14:51,399 --> 00:14:54,460 great way to put it. We have L for logarithmic 310 00:14:54,460 --> 00:15:00,000 space. We have P. polynomial time, p space, polynomial 311 00:15:00,000 --> 00:15:04,799 space, and xp. Watson maps them out as a nested 312 00:15:04,799 --> 00:15:07,039 chain. L is a subset of p, which is a subset 313 00:15:07,039 --> 00:15:09,919 of p space, which is a subset of xp. The causal 314 00:15:09,919 --> 00:15:12,259 links between these classes are really profound. 315 00:15:12,360 --> 00:15:15,279 Take L and p, for instance. If an algorithm operates 316 00:15:15,279 --> 00:15:18,320 in logarithmic space, its working memory is tiny. 317 00:15:18,399 --> 00:15:21,399 Very tiny. A program's total internal state is 318 00:15:21,399 --> 00:15:24,080 defined by what is currently in its memory, plus 319 00:15:24,080 --> 00:15:26,799 its current line of code. If the memory is strictly 320 00:15:26,799 --> 00:15:29,440 limited, the total number of unique states the 321 00:15:29,440 --> 00:15:32,139 program can possibly enter is also very small. 322 00:15:32,799 --> 00:15:34,740 Right, because a machine with three bits of memory 323 00:15:34,740 --> 00:15:37,559 can only represent eight distinct memory states. 324 00:15:38,279 --> 00:15:40,960 Exactly. And if the algorithm runs long enough, 325 00:15:41,200 --> 00:15:43,480 it will eventually exhaust all possible unique 326 00:15:43,480 --> 00:15:46,240 states. If it takes one more step after that, 327 00:15:46,559 --> 00:15:48,539 it must enter a state it has been in before. 328 00:15:48,940 --> 00:15:51,539 Which means it has entered an infinite loop? 329 00:15:51,860 --> 00:15:54,950 Yes. And since a valid algorithm must eventually 330 00:15:54,950 --> 00:15:57,610 halt and give an answer, a logarithmic space 331 00:15:57,610 --> 00:16:00,990 algorithm is strictly forced by its lack of memory 332 00:16:00,990 --> 00:16:04,169 to halt within polynomial time. Therefore, any 333 00:16:04,169 --> 00:16:07,190 problem solvable in L is mathematically guaranteed 334 00:16:07,190 --> 00:16:11,429 to be solvable in P. That is wild. A severe lack 335 00:16:11,429 --> 00:16:14,629 of space enforces a strict time limit. But going 336 00:16:14,629 --> 00:16:16,350 the other direction is where we hit one of the 337 00:16:16,350 --> 00:16:19,250 most elegant theorems in the book, I think. The 338 00:16:19,250 --> 00:16:22,440 T log T space bound theorem. Oh, this is a beautiful 339 00:16:22,440 --> 00:16:25,299 one. The theorem states that any problem you 340 00:16:25,299 --> 00:16:28,659 can solve in time t can be solved using a working 341 00:16:28,659 --> 00:16:31,919 memory space bounded by t log t. To understand 342 00:16:31,919 --> 00:16:33,879 this, we have to look at how programs normally 343 00:16:33,879 --> 00:16:37,000 use memory. An algorithm running for t steps 344 00:16:37,000 --> 00:16:40,419 can only possibly write to, at most, t distinct 345 00:16:40,419 --> 00:16:43,080 memory addresses. It only has t units of time 346 00:16:43,080 --> 00:16:46,549 to do the writing. Right. So why wouldn't the 347 00:16:46,549 --> 00:16:49,149 space bound just be t? Why is there a log t overhead? 348 00:16:49,509 --> 00:16:52,190 Because of fragmentation. A program running in 349 00:16:52,190 --> 00:16:55,169 time t might write to memory address 5 and then 350 00:16:55,169 --> 00:16:57,450 jump to address 1 million and then to address 351 00:16:57,450 --> 00:17:01,190 2 billion. I see. Our formal models measure space 352 00:17:01,190 --> 00:17:03,950 complexity by the highest memory address accessed 353 00:17:03,950 --> 00:17:06,369 because physically you have to allocate that 354 00:17:06,369 --> 00:17:08,130 entire block of memory just to reach the end 355 00:17:08,130 --> 00:17:10,769 of it. The space complexity would look massive 356 00:17:10,769 --> 00:17:13,329 even though 99 % of the memory is actually empty. 357 00:17:13,609 --> 00:17:15,990 So we have to like defragment the working memory 358 00:17:15,990 --> 00:17:18,809 on the fly. Precisely. We intercept the algorithm's 359 00:17:18,809 --> 00:17:21,809 memory requests and redirect them. We build a 360 00:17:21,809 --> 00:17:24,109 dictionary data structure in our limited memory. 361 00:17:24,529 --> 00:17:27,069 Okay. When the algorithm tries to write a value 362 00:17:27,069 --> 00:17:30,089 to address two billion, our dictionary intercepts 363 00:17:30,089 --> 00:17:33,170 it and says, nope, I am placing that value in 364 00:17:33,170 --> 00:17:36,369 contiguous slot number one. And it records the 365 00:17:36,369 --> 00:17:39,009 mapping. Original address two billion equals 366 00:17:39,009 --> 00:17:43,509 slot one. Okay, I see the catch though. You have 367 00:17:43,509 --> 00:17:45,990 to store the original address inside the dictionary 368 00:17:45,990 --> 00:17:48,910 as a key so you can find it later. If you have 369 00:17:48,910 --> 00:17:52,210 T entries, you need T keys. And to distinguish 370 00:17:52,210 --> 00:17:55,309 between T different keys, each key must be log 371 00:17:55,309 --> 00:17:57,990 T bits long. The math locks together perfectly. 372 00:17:58,410 --> 00:18:01,289 T contiguous slots, each requiring log T bits 373 00:18:01,289 --> 00:18:03,650 for the dictionary mapping overhead, result in 374 00:18:03,650 --> 00:18:06,230 a tightly packed memory footprint of exactly 375 00:18:06,230 --> 00:18:10,720 T log T space. We have formally proven that time 376 00:18:10,720 --> 00:18:14,359 T can always be compressed into space T log T. 377 00:18:14,700 --> 00:18:17,180 That translation from time to space is just beautiful. 378 00:18:17,769 --> 00:18:20,009 But theorists don't just translate resources, 379 00:18:20,049 --> 00:18:22,809 do they? They translate the problems themselves. 380 00:18:23,349 --> 00:18:25,609 The mechanism for this is called a reduction. 381 00:18:25,990 --> 00:18:28,190 It's like the glue holding all of complexity 382 00:18:28,190 --> 00:18:30,930 theory together. It absolutely is. A reduction 383 00:18:30,930 --> 00:18:33,410 translates a problem we don't understand into 384 00:18:33,410 --> 00:18:36,009 a problem we do understand. But we must establish 385 00:18:36,009 --> 00:18:39,250 a firm, unbreakable rule regarding directionality 386 00:18:39,250 --> 00:18:41,809 here. What's the rule? A reduction from problem 387 00:18:41,809 --> 00:18:45,569 A to problem B transfers an algorithm for B to 388 00:18:45,569 --> 00:18:48,599 A. If you have a fast solver for B, you now have 389 00:18:48,599 --> 00:18:52,029 a fast solver for A. Simultaneously, it transfers 390 00:18:52,029 --> 00:18:56,180 the hardness of A to B. If you know A is impossible, 391 00:18:56,539 --> 00:18:59,220 B must also be impossible. Okay, but it does 392 00:18:59,220 --> 00:19:01,839 not mean they are equal in difficulty. I think 393 00:19:01,839 --> 00:19:04,559 that's a common misconception. A reduction from 394 00:19:04,559 --> 00:19:08,460 A to B just proves that B is at least as hard 395 00:19:08,460 --> 00:19:11,720 as A. It's a lower bound. Exactly. And within 396 00:19:11,720 --> 00:19:14,740 this framework, Watson delineates mapping reductions 397 00:19:14,740 --> 00:19:18,200 and Oracle reductions. A mapping reduction is 398 00:19:18,200 --> 00:19:21,240 a strict one -way translation. You mold an instance 399 00:19:21,240 --> 00:19:24,599 of problem A into problem B, feed it to a hypothetical 400 00:19:24,599 --> 00:19:27,759 solver, an oracle, and whatever the oracle spits 401 00:19:27,759 --> 00:19:30,740 out is your final answer. No follow -up questions 402 00:19:30,740 --> 00:19:33,740 allowed. Like a one -shot deal. Whereas an oracle 403 00:19:33,740 --> 00:19:36,279 reduction is more like writing a software script 404 00:19:36,279 --> 00:19:39,259 that calls an external API. You can ask the API 405 00:19:39,259 --> 00:19:42,819 a question, get the answer. do some local processing, 406 00:19:43,079 --> 00:19:45,039 and then ask the API a different question based 407 00:19:45,039 --> 00:19:47,880 on that first answer. It's adaptive. Yes, and 408 00:19:47,880 --> 00:19:50,240 that adaptivity is crucial when we deal with 409 00:19:50,240 --> 00:19:52,400 the difference between a search problem and a 410 00:19:52,400 --> 00:19:54,819 decision problem. Let's return to the map routing 411 00:19:54,819 --> 00:19:57,940 problem to explain this. Is there a path from 412 00:19:57,940 --> 00:20:01,359 S to T is a decision problem? The answer is just 413 00:20:01,359 --> 00:20:05,059 yes or no. But what is the exact sequence of 414 00:20:05,059 --> 00:20:08,359 roads from S to T is a search problem. Right. 415 00:20:08,500 --> 00:20:10,740 Intuitively, it feels like the search problem 416 00:20:10,740 --> 00:20:14,240 must be vastly harder. A simple yes or no oracle 417 00:20:14,240 --> 00:20:16,559 doesn't give you the driving directions. But 418 00:20:16,559 --> 00:20:19,380 using an oracle reduction, we can actually squeeze 419 00:20:19,380 --> 00:20:21,740 the driving directions out of the yes or no oracle 420 00:20:21,740 --> 00:20:24,019 by playing a very targeted game of 20 questions. 421 00:20:24,400 --> 00:20:26,799 How does that work? We ask the oracle, is there 422 00:20:26,799 --> 00:20:30,059 a path from S to T? It says yes. We then look 423 00:20:30,059 --> 00:20:32,900 at the three roads leaving city S. They go to 424 00:20:32,900 --> 00:20:36,420 cities A, B, and C. We asked the Oracle three 425 00:20:36,420 --> 00:20:39,359 new questions. Is there a path from A to T, from 426 00:20:39,359 --> 00:20:43,720 B to T, from C to T? Oh, if it says yes for city 427 00:20:43,720 --> 00:20:46,240 B, you know the first leg of your route is to 428 00:20:46,240 --> 00:20:49,200 drive to B. You move to B, look at its neighbors, 429 00:20:49,420 --> 00:20:51,779 and quaylee the Oracle again. You just follow 430 00:20:51,779 --> 00:20:53,940 the breadcrumbs of yes answers all the way to 431 00:20:53,940 --> 00:20:57,200 the destination. Exactly. This search to decision 432 00:20:57,200 --> 00:20:59,819 reduction proves that finding the actual solution 433 00:20:59,819 --> 00:21:02,440 is not mathematically harder than merely deciding 434 00:21:02,440 --> 00:21:05,500 if a solution exists. By clumping problems together 435 00:21:05,500 --> 00:21:08,160 with reductions like this, theorists identified 436 00:21:08,160 --> 00:21:10,819 a massive equivalence class of problems that 437 00:21:10,819 --> 00:21:13,619 share the same fundamental difficulty. Which 438 00:21:13,619 --> 00:21:15,680 brings us to the most famous concept in the book, 439 00:21:15,900 --> 00:21:17,960 and really the grand challenge of computer science. 440 00:21:18,500 --> 00:21:21,619 P versus NP. It is literally the million dollar 441 00:21:21,619 --> 00:21:24,440 question posed by the Clay Mathematics Institute. 442 00:21:24,720 --> 00:21:28,109 Yep. So we already defined P as the class of 443 00:21:28,109 --> 00:21:30,369 decision problems with polynomial time solvers. 444 00:21:30,509 --> 00:21:32,630 These are problems we can efficiently figure 445 00:21:32,630 --> 00:21:36,049 out from scratch. NP is where the confusion usually 446 00:21:36,049 --> 00:21:39,089 starts, right? Because NP does not stand for 447 00:21:39,089 --> 00:21:42,549 not polynomial or inherently exponential. No, 448 00:21:42,609 --> 00:21:44,990 it doesn't. If we connect this to the bigger 449 00:21:44,990 --> 00:21:48,509 picture, NP actually stands for non -deterministic 450 00:21:48,509 --> 00:21:51,549 polynomial time. Okay, break that down for us. 451 00:21:52,009 --> 00:21:54,329 It means NP is the class of decision problems 452 00:21:54,329 --> 00:21:58,640 that have polynomial time verifiers. It is entirely 453 00:21:58,640 --> 00:22:01,579 about checking someone else's work. If I hand 454 00:22:01,579 --> 00:22:05,019 you a proposed solution, a witness, can you write 455 00:22:05,019 --> 00:22:07,859 a fast algorithm to verify that my solution is 456 00:22:07,859 --> 00:22:11,099 valid? Sudoku is the ultimate analogy here, right? 457 00:22:11,380 --> 00:22:14,119 Handing you a blank 9x9 grid and asking you to 458 00:22:14,119 --> 00:22:16,740 solve it requires search, logic, backtracking. 459 00:22:17,000 --> 00:22:19,339 It's hard. But if I hand you a completely filled 460 00:22:19,339 --> 00:22:22,400 out grid and claim I solved it, verifying my 461 00:22:22,400 --> 00:22:24,720 claim takes seconds. Right. You just scan the 462 00:22:24,720 --> 00:22:27,200 rows and columns for duplicates. Finding the 463 00:22:27,200 --> 00:22:29,920 solution is hard, but verifying it is fast. Therefore, 464 00:22:30,000 --> 00:22:33,960 Sudoku is in NP. And since any problem you can 465 00:22:33,960 --> 00:22:36,319 solve quickly from scratch, you know, class P, 466 00:22:36,660 --> 00:22:39,019 can obviously be verified quickly because you 467 00:22:39,019 --> 00:22:41,240 just solve it yourself and compare answers, we 468 00:22:41,240 --> 00:22:45,220 know that P is a subset of NP. Yes. The grand 469 00:22:45,220 --> 00:22:48,660 question asks if the reverse is true. If a problem's 470 00:22:48,660 --> 00:22:51,829 solution can be efficiently verified. Does that 471 00:22:51,829 --> 00:22:54,349 guarantee there is a mathematical trick to efficiently 472 00:22:54,349 --> 00:22:57,309 find the solution from scratch? Does P equal 473 00:22:57,309 --> 00:22:59,930 NP? Here's where it gets really interesting. 474 00:23:00,509 --> 00:23:03,529 Most experts heavily conjecture that P does not 475 00:23:03,529 --> 00:23:06,789 equal NP. They believe that creativity and the 476 00:23:06,789 --> 00:23:09,230 process of finding an answer cannot be universally 477 00:23:09,230 --> 00:23:11,529 mechanized into efficient computation. That's 478 00:23:11,529 --> 00:23:13,950 the prevailing belief, yes. But the sensationalism 479 00:23:13,950 --> 00:23:16,690 around this question drives me crazy. You see 480 00:23:16,690 --> 00:23:19,089 articles claiming that if someone proves P equals 481 00:23:19,089 --> 00:23:22,869 NP, it will instantly cure cancer, create artificial 482 00:23:22,869 --> 00:23:25,170 general intelligence overnight, and cause airplanes 483 00:23:25,170 --> 00:23:27,430 to fall out of the sky because all encryption 484 00:23:27,430 --> 00:23:29,970 will instantly break. We absolutely must separate 485 00:23:29,970 --> 00:23:32,990 theoretical vulnerability from practical apocalypse 486 00:23:32,990 --> 00:23:36,630 here. Thank you. Yes. If P equals NP, it would 487 00:23:36,630 --> 00:23:39,009 have staggering theoretical consequences, certainly. 488 00:23:39,539 --> 00:23:41,640 Computational cryptography relies on the fact 489 00:23:41,640 --> 00:23:45,460 that finding a key, search, is hard. But checking 490 00:23:45,460 --> 00:23:48,059 if a guest key decrypts the file, verification, 491 00:23:48,440 --> 00:23:51,420 is easy. So theoretically, breaking encryption 492 00:23:51,420 --> 00:23:55,720 is an NP problem. If P equals NP, a fast algorithm 493 00:23:55,720 --> 00:23:58,339 to break it is guaranteed to exist. But the guarantee 494 00:23:58,339 --> 00:24:00,759 of existence doesn't mean the algorithm is usable. 495 00:24:01,480 --> 00:24:04,779 The polynomial time algorithm to break RSA might... 496 00:24:04,819 --> 00:24:08,740 run in time n to the power of 5 ,000, it would 497 00:24:08,740 --> 00:24:10,799 theoretically be NP, but it would still take 498 00:24:10,799 --> 00:24:13,400 a trillion years to execute on a physical machine. 499 00:24:14,160 --> 00:24:16,059 Furthermore, it would not defeat information 500 00:24:16,059 --> 00:24:18,960 theoretic security, like the one -time pad, which 501 00:24:18,960 --> 00:24:21,339 relies on physical mathematical randomness rather 502 00:24:21,339 --> 00:24:23,700 than computational difficulty. Let's look at 503 00:24:23,700 --> 00:24:26,240 the flip side of that. Let's say someone publishes 504 00:24:26,240 --> 00:24:29,180 a valid proof tomorrow that P does not equal 505 00:24:29,180 --> 00:24:31,940 NP. Does that mean our modern cryptography is 506 00:24:31,940 --> 00:24:35,190 perfectly secure forever? Absolutely not. Proving 507 00:24:35,190 --> 00:24:38,329 P is not equal to NP only establishes that some 508 00:24:38,329 --> 00:24:41,730 problems in NP are hard to solve in the absolute 509 00:24:41,730 --> 00:24:44,710 worst case scenario. Okay, wait, so just some 510 00:24:44,710 --> 00:24:47,230 problems? Right. It doesn't prove that factoring 511 00:24:47,230 --> 00:24:49,529 large primes, which is the bedrock of modern 512 00:24:49,529 --> 00:24:52,569 encryption, is one of those hard problems. And 513 00:24:52,569 --> 00:24:54,549 even if factoring is hard in the worst case, 514 00:24:54,970 --> 00:24:57,130 cryptography requires it to be hard on average 515 00:24:57,130 --> 00:25:00,859 for almost all random keys. P not equaling NP 516 00:25:00,859 --> 00:25:02,900 alone does not establish average case hardness 517 00:25:02,900 --> 00:25:05,819 or the existence of secure one -way functions. 518 00:25:06,400 --> 00:25:08,920 It is a necessary foundation, but it doesn't 519 00:25:08,920 --> 00:25:11,920 build the whole house. Okay, so within that massive 520 00:25:11,920 --> 00:25:15,660 class of NP problems, theorists used reductions 521 00:25:15,660 --> 00:25:18,619 to find the hardest problems of all, the NP -complete 522 00:25:18,619 --> 00:25:21,799 problems. Yes, an NP -complete problem is the 523 00:25:21,799 --> 00:25:24,140 ultimate bottleneck. Through mapping reductions, 524 00:25:24,400 --> 00:25:26,759 we have proven that every single problem in NP 525 00:25:26,970 --> 00:25:30,150 can be mathematically translated into any NP 526 00:25:30,150 --> 00:25:33,089 -complete problem. So if you find a fast solver 527 00:25:33,089 --> 00:25:36,789 for just one NP -complete problem, like SAT or 528 00:25:36,789 --> 00:25:39,750 the traveling salesperson problem, you can use 529 00:25:39,750 --> 00:25:42,170 reductions to quickly solve every problem in 530 00:25:42,170 --> 00:25:46,269 NP. You would prove P equals NP. Exactly. But 531 00:25:46,269 --> 00:25:48,430 because thousands of brilliant mathematicians 532 00:25:48,430 --> 00:25:50,809 have slammed their heads against SAT for decades 533 00:25:50,809 --> 00:25:53,069 and failed, they realized they needed a different 534 00:25:53,069 --> 00:25:55,130 way to prove that some problems are harder than 535 00:25:55,130 --> 00:25:57,900 others. They needed to build formal hierarchies. 536 00:25:58,160 --> 00:26:00,440 Right. And if you want to mathematically prove 537 00:26:00,440 --> 00:26:03,240 that granting an algorithm strictly more time 538 00:26:03,240 --> 00:26:05,779 allows it to solve strictly more problems, you 539 00:26:05,779 --> 00:26:10,140 employ a technique called diagonalization. Diagonalization. 540 00:26:10,740 --> 00:26:12,559 Ellen Turing adapted this concept from Garret 541 00:26:12,559 --> 00:26:15,420 Conter's work on the differing sizes of infinity 542 00:26:15,420 --> 00:26:18,460 in set theory. How exactly do you diagonalize 543 00:26:18,460 --> 00:26:21,460 an algorithm? You construct a paradox. you create 544 00:26:21,460 --> 00:26:23,940 a purpose -built problem explicitly designed 545 00:26:23,940 --> 00:26:27,000 to thwart any algorithm constrained by a specific 546 00:26:27,000 --> 00:26:29,740 resource limit. Okay, give me an example. Suppose 547 00:26:29,740 --> 00:26:32,279 we want to prove that an algorithm with n -cubed 548 00:26:32,279 --> 00:26:34,779 time is strictly more powerful than any algorithm 549 00:26:34,779 --> 00:26:37,960 limited to n -squared time. We write a master 550 00:26:37,960 --> 00:26:41,259 algorithm. This master algorithm takes any n 551 00:26:41,259 --> 00:26:44,339 -squared algorithm's code as its input, simulates 552 00:26:44,339 --> 00:26:47,160 it, and then deliberately outputs the exact opposite 553 00:26:47,160 --> 00:26:49,599 of what the simulated algorithm predicted. It's 554 00:26:49,599 --> 00:26:52,339 an incredibly spiteful piece of code. It just 555 00:26:52,339 --> 00:26:54,839 waits to see what the weaker algorithm will do 556 00:26:54,839 --> 00:26:57,079 and then mathematically chooses the opposite. 557 00:26:57,440 --> 00:27:01,059 It is spiteful, but it works perfectly. The master 558 00:27:01,059 --> 00:27:03,680 algorithm guarantees that it disagrees with every 559 00:27:03,680 --> 00:27:06,640 single n -squared algorithm on at least one input. 560 00:27:07,240 --> 00:27:10,000 Therefore, the problem the master algorithm is 561 00:27:10,000 --> 00:27:12,559 solving cannot possibly be solved by any n -squared 562 00:27:12,559 --> 00:27:15,980 algorithm. Wow. However, because the master algorithm 563 00:27:15,980 --> 00:27:18,440 needs a little extra overhead to run the simulation, 564 00:27:18,980 --> 00:27:22,059 It requires slightly more time, n cubed time. 565 00:27:22,759 --> 00:27:25,980 Thus, we rigorously prove that time n cubed is 566 00:27:25,980 --> 00:27:28,180 strictly larger and more capable than time n 567 00:27:28,180 --> 00:27:31,640 squared. So you establish a firm time hierarchy. 568 00:27:32,240 --> 00:27:35,259 And a similar proof establishes the space hierarchy. 569 00:27:35,819 --> 00:27:39,059 But these hierarchies rely on uniform algorithms. 570 00:27:39,559 --> 00:27:42,180 A uniform algorithm is a single universal piece 571 00:27:42,180 --> 00:27:44,880 of code that has to handle an input of any size. 572 00:27:45,579 --> 00:27:48,400 Watson introduces a massive pivot in the text 573 00:27:48,400 --> 00:27:52,539 here, moving to non -uniformity. Yes. Non -uniformity 574 00:27:52,539 --> 00:27:56,299 is a total paradigm shift. We abandon the idea 575 00:27:56,299 --> 00:27:59,519 of a single piece of code. Instead, we allow 576 00:27:59,519 --> 00:28:01,700 a completely different custom -built algorithm 577 00:28:01,700 --> 00:28:04,299 for every single input size. And the mathematical 578 00:28:04,299 --> 00:28:07,039 model we use to represent non -uniform computation 579 00:28:07,039 --> 00:28:09,700 is logic circuits, right? The physical wiring 580 00:28:09,700 --> 00:28:12,920 of AND gates, OR gates, and NOT gates. Exactly. 581 00:28:13,140 --> 00:28:16,519 A circuit is inherently non -uniform because 582 00:28:16,519 --> 00:28:19,279 a specific layout of logic gates has a fixed 583 00:28:19,279 --> 00:28:22,279 number of input pins. A circuit wired to accept 584 00:28:22,279 --> 00:28:26,500 a 32 -bit input physically cannot process a 33 585 00:28:26,500 --> 00:28:29,559 -bit input. So the class of problems solvable 586 00:28:29,559 --> 00:28:32,500 by polynomial -sized circuits is called p -poly. 587 00:28:33,019 --> 00:28:35,599 But why do theorists even care about this? Software 588 00:28:35,599 --> 00:28:37,940 in the real world is uniform. My spreadsheet 589 00:28:37,940 --> 00:28:40,019 app doesn't swap out its source code depending 590 00:28:40,019 --> 00:28:42,730 on how many rows of data I paste into it. Well, 591 00:28:42,769 --> 00:28:45,730 from a practical engineering standpoint, uniformity 592 00:28:45,730 --> 00:28:49,049 is required. But from a theoretical standpoint, 593 00:28:49,690 --> 00:28:51,910 specifically for proving lower bounds, proving 594 00:28:51,910 --> 00:28:55,410 what computers can't do, non -uniform circuits 595 00:28:55,410 --> 00:28:58,069 are the ultimate analytical weapon. Why's that? 596 00:28:58,930 --> 00:29:01,349 A custom -built circuit for a specific input 597 00:29:01,349 --> 00:29:04,009 size is extraordinarily powerful. It doesn't 598 00:29:04,009 --> 00:29:07,250 waste time looping, tracking variables, or computing 599 00:29:07,250 --> 00:29:10,279 the length of the input. All that software bloat 600 00:29:10,279 --> 00:29:13,440 is stripped away, leaving only pure combinational 601 00:29:13,440 --> 00:29:16,970 logic. We can rigorously prove that any uniform 602 00:29:16,970 --> 00:29:20,009 program running in time t can have its fetch 603 00:29:20,009 --> 00:29:22,470 -execute cycle unrolled into a combinational 604 00:29:22,470 --> 00:29:25,289 logic circuit of size roughly t squared times 605 00:29:25,289 --> 00:29:28,589 folly log t. So a circuit is basically a strictly 606 00:29:28,589 --> 00:29:31,089 more powerful, streamlined version of an algorithm. 607 00:29:31,390 --> 00:29:33,250 If you can mathematically prove that a problem 608 00:29:33,250 --> 00:29:36,150 is so incredibly difficult, it cannot even be 609 00:29:36,150 --> 00:29:38,420 solved by custom -built non -uniform circuits 610 00:29:38,420 --> 00:29:41,599 of polynomial size, then it definitively cannot 611 00:29:41,599 --> 00:29:44,240 be solved by a normal uniform algorithm either. 612 00:29:44,619 --> 00:29:47,660 Exactly. It provides a pristine, stripped -down 613 00:29:47,660 --> 00:29:50,299 mathematical model to aim our proofs at. Now, 614 00:29:50,539 --> 00:29:53,000 when defining circuit models, we must make a 615 00:29:53,000 --> 00:29:55,960 precise distinction between bounded and unbounded 616 00:29:55,960 --> 00:29:59,160 fan -in. Fan -in being the number of input wires 617 00:29:59,160 --> 00:30:02,400 feeding into a single logic gate? Right. A bounded 618 00:30:02,400 --> 00:30:05,079 fan -in circuit restricts an AND gate to taking, 619 00:30:05,079 --> 00:30:08,450 say, two inputs. An unbounded fan -in circuit 620 00:30:08,450 --> 00:30:10,710 allows a single AND gate to take an infinite 621 00:30:10,710 --> 00:30:13,630 number of inputs. But to be clear to the listener, 622 00:30:14,089 --> 00:30:17,089 unbounded fan -in is not permission for arbitrary 623 00:30:17,089 --> 00:30:20,029 magic gates. An unbounded AND gate with a million 624 00:30:20,029 --> 00:30:23,170 inputs still only outputs a one if every single 625 00:30:23,170 --> 00:30:25,990 one of those million inputs is a one. It's standard 626 00:30:25,990 --> 00:30:28,529 Boolean logic, just flattened out. That flattening 627 00:30:28,529 --> 00:30:31,269 is key. It's how complexity theory perfectly 628 00:30:31,269 --> 00:30:34,220 models parallel processing. When we look at flattened 629 00:30:34,220 --> 00:30:36,640 circuits, we discover the first concrete massive 630 00:30:36,640 --> 00:30:39,559 breakthrough, improving lower bounds. We enter 631 00:30:39,559 --> 00:30:42,720 the hierarchies of parallel time, the NC hierarchy 632 00:30:42,720 --> 00:30:46,440 and the AC hierarchy. NC stands for NICS class, 633 00:30:46,680 --> 00:30:49,640 modeling circuits with bounded fan -in. AC stands 634 00:30:49,640 --> 00:30:52,720 for alternating circuits, which allow the unbounded 635 00:30:52,720 --> 00:30:55,440 fan -in gates. Yes. And these hierarchies are 636 00:30:55,440 --> 00:30:57,460 categorized by the depth of the circuit, how 637 00:30:57,460 --> 00:30:59,740 many layers of gates a signal has to pass through 638 00:30:59,740 --> 00:31:02,180 from the input pins to the final output wire. 639 00:31:02,730 --> 00:31:05,329 Depth corresponds directly to time, because all 640 00:31:05,329 --> 00:31:07,410 the gates in a single layer can process their 641 00:31:07,410 --> 00:31:10,869 logic simultaneously in one clock cycle. Let's 642 00:31:10,869 --> 00:31:13,349 focus on the absolute bottom of the AC hierarchy, 643 00:31:13,990 --> 00:31:17,470 AC0. These are circuits that allow unbounded 644 00:31:17,470 --> 00:31:20,269 fan -in. Gates can have infinite inputs, but 645 00:31:20,269 --> 00:31:22,710 the overall circuit is restricted to a strictly 646 00:31:22,710 --> 00:31:26,950 constant depth. OK, I think of AC0 as a massive 647 00:31:26,950 --> 00:31:29,049 corporate hierarchy with incre... incredibly 648 00:31:29,049 --> 00:31:31,450 flat management. You have layers of managers 649 00:31:31,450 --> 00:31:34,109 reporting to directors. Because it's unbounded 650 00:31:34,109 --> 00:31:36,349 fan -in, a single manager can have an infinite 651 00:31:36,349 --> 00:31:39,390 number of direct reports. But because it's constant 652 00:31:39,390 --> 00:31:42,009 depth, the company is strictly limited to only 653 00:31:42,009 --> 00:31:44,569 two or three layers of management total. That's 654 00:31:44,569 --> 00:31:47,230 a perfect analogy. And what's fascinating is 655 00:31:47,230 --> 00:31:49,650 finding out what that shallow management structure 656 00:31:49,650 --> 00:31:53,119 is mathematically incapable of doing. Watson 657 00:31:53,119 --> 00:31:55,680 highlights landmark theorem here. The parity 658 00:31:55,680 --> 00:31:58,859 function is definitively outside the class AC0. 659 00:31:59,359 --> 00:32:02,099 The parity function is remarkably simple to describe, 660 00:32:02,559 --> 00:32:05,220 too. Given a string of ones and zeros, is the 661 00:32:05,220 --> 00:32:08,319 total number of ones an odd number? That's it. 662 00:32:08,720 --> 00:32:11,259 It's a basic counting task. But the theorem proves 663 00:32:11,259 --> 00:32:13,440 that even if you have polynomial -sized circuits, 664 00:32:13,980 --> 00:32:16,740 and even if you allow unbounded fan in, where 665 00:32:16,740 --> 00:32:19,119 a single logic gate can look at a million inputs 666 00:32:19,119 --> 00:32:22,819 simultaneously, if you restrict them to a constant 667 00:32:22,819 --> 00:32:26,130 depth, They simply cannot compute parity. Walk 668 00:32:26,130 --> 00:32:28,349 us through the intuition of that proof. Why does 669 00:32:28,349 --> 00:32:31,650 constant depth fail so spectacularly at a simple 670 00:32:31,650 --> 00:32:34,650 counting task? It relies on techniques called 671 00:32:34,650 --> 00:32:37,450 switching lemmas. The core issue is that shallow 672 00:32:37,450 --> 00:32:40,150 circuits cannot reliably propagate localized 673 00:32:40,150 --> 00:32:43,789 changes. In the parity function, flipping a single 674 00:32:43,789 --> 00:32:46,210 bit anywhere in the input instantly flips the 675 00:32:46,210 --> 00:32:48,509 final answer of the entire function. Right. If 676 00:32:48,509 --> 00:32:52,160 a circuit has constant depth, the managers simply 677 00:32:52,160 --> 00:32:54,240 do not have enough layers of communication to 678 00:32:54,240 --> 00:32:57,160 synthesize the global state of the input. If 679 00:32:57,160 --> 00:32:59,519 you mathematically restrict a few of the input 680 00:32:59,519 --> 00:33:02,720 pins, the constant depth circuit completely collapses 681 00:33:02,720 --> 00:33:06,200 and loses all its structural complexity. It cannot 682 00:33:06,200 --> 00:33:09,259 reliably carry the signal of a single bit flip 683 00:33:09,259 --> 00:33:12,819 across the entire board. Parity is strictly outside 684 00:33:12,819 --> 00:33:16,140 AC0. Okay, hold on. If we just mathematically 685 00:33:16,140 --> 00:33:19,339 proved that parity is outside AC0, why on earth 686 00:33:19,339 --> 00:33:21,789 can't we just take that exact same math turn 687 00:33:21,789 --> 00:33:24,630 the dial up a bit and apply it to SAT. If we 688 00:33:24,630 --> 00:33:27,029 prove SAT is outside P slash poly, doesn't that 689 00:33:27,029 --> 00:33:30,069 just solve P versus NP right there? That was 690 00:33:30,069 --> 00:33:32,430 exactly the sentiment in the 1980s. There was 691 00:33:32,430 --> 00:33:35,009 immense optimism. Theorists thought they had 692 00:33:35,009 --> 00:33:37,150 the blueprint and they just needed to scale the 693 00:33:37,150 --> 00:33:39,970 math to deeper circuits. So what happened? The 694 00:33:39,970 --> 00:33:42,170 switching lemmas fundamentally rely on the circuit 695 00:33:42,170 --> 00:33:44,670 being shallow. When you attempt to apply those 696 00:33:44,670 --> 00:33:47,609 same mathematical levers to circuits with logarithmic 697 00:33:47,609 --> 00:33:51,339 depth or general polynomial size, the math simply 698 00:33:51,339 --> 00:33:54,500 evaporates. The tools are explicitly calibrated 699 00:33:54,500 --> 00:33:57,200 for flat structures. So we built a ladder that 700 00:33:57,200 --> 00:33:59,220 got us to the roof, but we can't use that same 701 00:33:59,220 --> 00:34:01,319 ladder to reach the moon. The physics of the 702 00:34:01,319 --> 00:34:03,480 tool are just wrong. And before the theorists 703 00:34:03,480 --> 00:34:05,240 could figure out how to build a spaceship, they 704 00:34:05,240 --> 00:34:07,279 had to deal with a wild card that completely 705 00:34:07,279 --> 00:34:09,219 changed the rules of algorithmic efficiency. 706 00:34:10,119 --> 00:34:13,059 Randomness. Everything we've modeled so far is 707 00:34:13,059 --> 00:34:15,780 deterministic. An algorithm gets an input and 708 00:34:15,780 --> 00:34:18,500 follows strict steps to an output. But if we 709 00:34:18,500 --> 00:34:20,679 give the algorithm the ability to flip a coin, 710 00:34:20,860 --> 00:34:24,739 During its execution, we enter randomized computation. 711 00:34:25,460 --> 00:34:28,119 And the central complexity class here is BPP, 712 00:34:28,880 --> 00:34:31,539 bounded error probabilistic polynomial time. 713 00:34:32,239 --> 00:34:34,679 Let's establish strict boundaries for what BPP 714 00:34:34,679 --> 00:34:38,059 actually means. The algorithm uses randomness, 715 00:34:38,380 --> 00:34:41,159 runs in polynomial time, and produces the correct 716 00:34:41,159 --> 00:34:44,380 answer with a bounded error probability for every 717 00:34:44,380 --> 00:34:47,389 single possible input. For every input is the 718 00:34:47,389 --> 00:34:50,030 crucial constraint there, right? A BPP algorithm 719 00:34:50,030 --> 00:34:53,389 does not just work well on most or average inputs. 720 00:34:53,650 --> 00:34:55,909 If the error bound is one third, it means that 721 00:34:55,909 --> 00:34:58,329 even if an adversary hands the algorithm the 722 00:34:58,329 --> 00:35:01,070 absolute worst case, most pathological, most 723 00:35:01,070 --> 00:35:04,090 difficult input imaginable, the algorithm will 724 00:35:04,090 --> 00:35:06,630 still output the correct answer at least two 725 00:35:06,630 --> 00:35:09,409 thirds of the time, purely because its internal 726 00:35:09,409 --> 00:35:12,269 coin flips protect it from being cornered. Watson 727 00:35:12,269 --> 00:35:14,849 uses a great analogy of polling of voter list. 728 00:35:15,309 --> 00:35:18,250 If you have a list of a million voters and you 729 00:35:18,250 --> 00:35:21,099 deterministically query the first thousand, a 730 00:35:21,099 --> 00:35:23,860 worst -case scenario could ruin you if the list 731 00:35:23,860 --> 00:35:26,420 happens to be sorted by income or geography. 732 00:35:26,719 --> 00:35:29,539 Your sample is horribly biased. Right. But if 733 00:35:29,539 --> 00:35:32,280 you randomly shuffle the list first, using internal 734 00:35:32,280 --> 00:35:34,739 coin flips, and then query the first thousand, 735 00:35:35,199 --> 00:35:37,739 the worst -case sorting bias is mathematically 736 00:35:37,739 --> 00:35:40,769 destroyed. The principles of probability guarantee 737 00:35:40,769 --> 00:35:43,190 that a random sample will accurately reflect 738 00:35:43,190 --> 00:35:45,849 the whole population, regardless of how the adversary 739 00:35:45,849 --> 00:35:48,210 ordered the original list. This raises an important 740 00:35:48,210 --> 00:35:50,010 question though, and it's a vital distinction 741 00:35:50,010 --> 00:35:53,510 to make. A lot of people confuse randomized algorithms 742 00:35:53,510 --> 00:35:57,409 with heuristics, or average case analysis. How 743 00:35:57,409 --> 00:36:00,170 are they different? They are entirely different 744 00:36:00,170 --> 00:36:03,429 paradigms. In a randomized algorithm, like BPP, 745 00:36:04,090 --> 00:36:07,409 the input is assumed to be worst case. but the 746 00:36:07,409 --> 00:36:10,670 algorithm's internal choices are random. In a 747 00:36:10,670 --> 00:36:13,650 heuristic, the algorithm is completely deterministic, 748 00:36:14,110 --> 00:36:16,389 but the math assumes the input is drawn from 749 00:36:16,389 --> 00:36:20,489 a benign random distribution. Okay, I see. Heuristics 750 00:36:20,489 --> 00:36:23,630 are useful in practice, but a heuristic will 751 00:36:23,630 --> 00:36:26,309 fail completely if handed a pathological input, 752 00:36:26,929 --> 00:36:29,630 and worst -case inputs do occur in the real world. 753 00:36:30,389 --> 00:36:33,739 BPP guarantees protection against them. But if 754 00:36:33,739 --> 00:36:37,360 a BPP algorithm makes errors, even just a third 755 00:36:37,360 --> 00:36:39,739 of the time, I don't want it running the navigation 756 00:36:39,739 --> 00:36:42,079 software on my commercial flight, I don't want 757 00:36:42,079 --> 00:36:44,539 a 1 in 3 chance of crashing, how do we trust 758 00:36:44,539 --> 00:36:48,019 this? We trust it through amplification. Because 759 00:36:48,019 --> 00:36:50,599 the algorithm is fast, we don't just run it once. 760 00:36:50,980 --> 00:36:54,059 We run it, say, 100 independent times on the 761 00:36:54,059 --> 00:36:56,599 same input, and we take the majority vote of 762 00:36:56,599 --> 00:37:00,639 the 100 outputs. And that works? Yes. Because 763 00:37:00,639 --> 00:37:03,159 the initial error was strictly bounded away from 764 00:37:03,159 --> 00:37:05,980 one half, the mathematics of independent random 765 00:37:05,980 --> 00:37:08,559 variables dictates that the chance of the majority 766 00:37:08,559 --> 00:37:11,880 vote being wrong decays exponentially. So it 767 00:37:11,880 --> 00:37:14,460 drops from one in three to an astronomically 768 00:37:14,460 --> 00:37:17,900 small fraction. Exactly. We avoid sensational 769 00:37:17,900 --> 00:37:20,599 meteor strike analogies in this field, but mathematically, 770 00:37:21,000 --> 00:37:23,760 the probability of the amplified algorithm failing 771 00:37:23,960 --> 00:37:26,420 becomes vastly smaller than the probability of 772 00:37:26,420 --> 00:37:28,440 a physical hardware failure in the processor 773 00:37:28,440 --> 00:37:32,179 itself. It basically becomes practically infallible. 774 00:37:32,440 --> 00:37:35,039 But here's where complexity theory throws a curveball. 775 00:37:35,679 --> 00:37:37,659 Despite the incredible power of coin tosses, 776 00:37:38,219 --> 00:37:40,920 it is not currently known if BPP is actually 777 00:37:40,920 --> 00:37:44,880 any larger than P. In fact, the prevailing conjecture 778 00:37:44,880 --> 00:37:49,280 is that P equals BPP. Yes. Theorists widely believe 779 00:37:49,280 --> 00:37:51,780 that every single randomized algorithm can be 780 00:37:51,780 --> 00:37:54,960 completely de -randomized. Randomness helps us 781 00:37:54,960 --> 00:37:57,599 find algorithms more easily, but it is not proven 782 00:37:57,599 --> 00:37:59,760 to be universally superior. So you're saying 783 00:37:59,760 --> 00:38:02,079 if a problem can be solved efficiently with coin 784 00:38:02,079 --> 00:38:05,139 tosses, there exists a clever deterministic algorithm 785 00:38:05,139 --> 00:38:07,360 that can solve it just as efficiently without 786 00:38:07,360 --> 00:38:10,320 them. That is the belief. We see a glimpse of 787 00:38:10,320 --> 00:38:12,440 this de -randomization through the shifting technique, 788 00:38:12,900 --> 00:38:15,539 which proves that BPP is a subset of P -poly, 789 00:38:15,980 --> 00:38:18,099 the non -uniform circuit class we talked about. 790 00:38:18,360 --> 00:38:20,739 Walk us through the shifting technique. How do 791 00:38:20,739 --> 00:38:22,719 we prove that a circuit can simulate coin flips? 792 00:38:23,019 --> 00:38:25,940 We use the probabilistic method. Imagine the 793 00:38:25,940 --> 00:38:28,659 space of all possible random coin flip sequences 794 00:38:28,659 --> 00:38:32,159 is a massive grid. For any specific input, the 795 00:38:32,159 --> 00:38:34,199 vast majority of those sequences lead to the 796 00:38:34,199 --> 00:38:36,960 correct answer. The bad sequences are a tiny 797 00:38:36,960 --> 00:38:39,559 fraction. Okay, I'm picturing it. The mathematical 798 00:38:39,559 --> 00:38:41,880 proof demonstrates that because the error rate 799 00:38:41,880 --> 00:38:44,440 is strictly bounded, you can take a small set 800 00:38:44,440 --> 00:38:47,539 of good sequences, mathematically shift them 801 00:38:47,539 --> 00:38:50,369 by applying an XOR operation, and prove that 802 00:38:50,369 --> 00:38:52,809 their intersection covers the entire grid of 803 00:38:52,809 --> 00:38:56,170 all possible inputs. Meaning there exists at 804 00:38:56,170 --> 00:38:59,210 least one specific hard -coded sequence of pseudo 805 00:38:59,210 --> 00:39:01,510 -random coin flips that will magically yield 806 00:39:01,510 --> 00:39:03,750 the correct answer for every single possible 807 00:39:03,750 --> 00:39:07,269 input of a given size. Exactly. You don't need 808 00:39:07,269 --> 00:39:09,789 to roll dice at runtime. You just bake that one 809 00:39:09,789 --> 00:39:12,110 perfect sequence into the non -uniform circuit 810 00:39:12,110 --> 00:39:15,289 as advice. It rigorously proves that BPP can 811 00:39:15,289 --> 00:39:17,690 be simulated by non -uniform circuits without 812 00:39:17,690 --> 00:39:20,469 active randomness. But if we truly believe P 813 00:39:20,469 --> 00:39:24,130 equals BPP for uniform algorithms, we must believe 814 00:39:24,130 --> 00:39:26,550 we can mathematically generate pseudorandomness 815 00:39:26,550 --> 00:39:29,489 to replace true coin flips entirely. Which brings 816 00:39:29,489 --> 00:39:33,150 us to extractors, PRGs, and the PCP theorem. 817 00:39:33,530 --> 00:39:36,519 Right. If you want to de -randomize an algorithm, 818 00:39:37,039 --> 00:39:39,059 you need a source of bits that look random but 819 00:39:39,059 --> 00:39:43,260 are fully deterministic. Enter pseudorandom generators, 820 00:39:43,519 --> 00:39:47,000 or PRGs. We must be highly rigorous with our 821 00:39:47,000 --> 00:39:50,619 definitions here. Cryptographic PRG takes a very 822 00:39:50,619 --> 00:39:54,000 small, truly random seed and stretches it into 823 00:39:54,000 --> 00:39:56,639 a massive string of bits. But those output bits 824 00:39:56,639 --> 00:39:59,219 are not literally mathematically random. They 825 00:39:59,219 --> 00:40:01,880 are entirely deterministic based on the seed. 826 00:40:02,260 --> 00:40:04,920 Correct. The security definition is based on 827 00:40:04,920 --> 00:40:07,539 computational indistinguishability. When a PRG 828 00:40:07,539 --> 00:40:10,340 is secure under its stated assumptions, its outputs 829 00:40:10,340 --> 00:40:12,960 are computationally indistinguishable from uniform 830 00:40:12,960 --> 00:40:16,579 randomness up to a small distinguishing advantage 831 00:40:16,579 --> 00:40:19,369 for an adversary. So we can introduce the concept 832 00:40:19,369 --> 00:40:22,590 of Kolmogorov complexity here, right? It measures 833 00:40:22,590 --> 00:40:25,230 how compressible a string of data is. A truly 834 00:40:25,230 --> 00:40:28,130 random string of a million coin flips is incompressible. 835 00:40:28,409 --> 00:40:30,949 You need a million bits to describe it. But the 836 00:40:30,949 --> 00:40:34,329 output of a PRG is highly compressible. Its Kolmogorov 837 00:40:34,329 --> 00:40:36,630 complexity is just the length of its tiny seed. 838 00:40:37,329 --> 00:40:39,329 Mathematically, the two strings are fundamentally 839 00:40:39,329 --> 00:40:42,030 different. That is The perfect way to frame it. 840 00:40:42,329 --> 00:40:44,769 Mathematically, the PRG output is highly structured, 841 00:40:45,210 --> 00:40:48,469 but computationally, to any polynomial time algorithm, 842 00:40:48,590 --> 00:40:51,670 it looks incompressible. What about extractors? 843 00:40:52,070 --> 00:40:53,969 Extractors operate in a similar but distinct 844 00:40:53,969 --> 00:40:56,769 space. In the real world, hardware randomness, 845 00:40:57,130 --> 00:40:59,610 like keystroke timings or thermal noise, is biased. 846 00:41:00,429 --> 00:41:02,369 Extractors are mathematical functions that take 847 00:41:02,369 --> 00:41:05,010 this biased data and produce distributions that 848 00:41:05,010 --> 00:41:08,420 are close to uniform under stated entropy assumptions. 849 00:41:08,900 --> 00:41:11,059 They don't magically create perfect randomness 850 00:41:11,059 --> 00:41:13,300 from nothing. They distill existing entropy. 851 00:41:13,780 --> 00:41:15,719 And this concept of randomness fundamentally 852 00:41:15,719 --> 00:41:18,260 revolutionized how we verify proofs, leading 853 00:41:18,260 --> 00:41:21,119 to the PCP theorem, probabilistically checkable 854 00:41:21,119 --> 00:41:23,440 proofs. When I read this section of the textbook, 855 00:41:23,659 --> 00:41:26,960 it completely broke my intuition. The PCP theorem 856 00:41:26,960 --> 00:41:30,119 is arguably the crowning achievement of complexity 857 00:41:30,119 --> 00:41:34,090 theory in the 1990s. We defined NP earlier as 858 00:41:34,090 --> 00:41:37,619 the class of problems where a solution or proof, 859 00:41:38,159 --> 00:41:40,519 can be verified efficiently in polynomial time. 860 00:41:41,619 --> 00:41:44,539 The PCP theorem states that any problem in NP 861 00:41:44,539 --> 00:41:47,579 can be verified by a randomized algorithm that 862 00:41:47,579 --> 00:41:50,199 reads only a constant number of bits of the proof. 863 00:41:50,619 --> 00:41:54,079 I need to pause on that. A constant number, like 864 00:41:54,079 --> 00:41:57,059 O of one bits. You're saying if a mathematical 865 00:41:57,059 --> 00:42:00,179 proof is a billion pages long, the verifier only 866 00:42:00,179 --> 00:42:03,139 needs to look at, say, three bits of data, and 867 00:42:03,139 --> 00:42:06,250 it can guarantee, with high probability, whether 868 00:42:06,250 --> 00:42:09,250 the billion -page proof is valid or fake, how 869 00:42:09,250 --> 00:42:13,610 is that even logically possible? It is entirely 870 00:42:13,610 --> 00:42:16,530 counterintuitive. It works by forcing the prover 871 00:42:16,530 --> 00:42:19,630 to format the proof in a highly redundant error 872 00:42:19,630 --> 00:42:22,750 -correcting code, often utilizing polynomial 873 00:42:22,750 --> 00:42:25,190 extensions. Okay, so they can't just hand in 874 00:42:25,190 --> 00:42:28,630 a normal paper. Right. The prover takes the standard 875 00:42:28,630 --> 00:42:30,829 proof and mathematically smears the information 876 00:42:30,829 --> 00:42:34,519 across the entire document. Because of this rigid 877 00:42:34,519 --> 00:42:37,099 interconnected structure, if there is a single 878 00:42:37,099 --> 00:42:39,300 logical error anywhere in the original proof, 879 00:42:39,780 --> 00:42:41,920 the error -correcting encoding propagates that 880 00:42:41,920 --> 00:42:44,920 error outward, corrupting almost the entire document. 881 00:42:45,300 --> 00:42:49,260 Ooh. A single lie becomes a global infection. 882 00:42:49,480 --> 00:42:53,539 Exactly. The verifier uses O of log n true randomness 883 00:42:53,539 --> 00:42:56,389 to select which three bits to look at. Because 884 00:42:56,389 --> 00:42:58,590 any local error in the original proof has been 885 00:42:58,590 --> 00:43:01,590 globally smeared, almost any three random bits 886 00:43:01,590 --> 00:43:04,329 the verifier checks will immediately flag a mathematical 887 00:43:04,329 --> 00:43:07,829 inconsistency. This theorem doesn't just revolutionize 888 00:43:07,829 --> 00:43:10,889 verification, it preserves gaps in approximation, 889 00:43:11,190 --> 00:43:13,210 which is why it's the foundational tool for proving 890 00:43:13,210 --> 00:43:15,829 that certain optimization problems are mathematically 891 00:43:15,829 --> 00:43:20,110 impossible to even approximate efficiently. So 892 00:43:20,110 --> 00:43:22,889 what does this all mean for security? Given all 893 00:43:22,889 --> 00:43:25,289 this power of randomness and pseudo -randomness, 894 00:43:25,679 --> 00:43:28,340 Does this mean adversaries are completely powerless 895 00:43:28,340 --> 00:43:31,400 against modern hashing and cryptography? No, 896 00:43:31,539 --> 00:43:34,380 and we must clarify that strictly. Security always 897 00:43:34,380 --> 00:43:36,840 depends on the mathematical model and the underlying 898 00:43:36,840 --> 00:43:40,099 assumptions. Randomization makes specific attacks 899 00:43:40,099 --> 00:43:43,159 harder, but it does not render every adversary 900 00:43:43,159 --> 00:43:46,780 powerless. Because it's conditional? Yes. If 901 00:43:46,780 --> 00:43:49,030 your underlying assumption, like the difficulty 902 00:43:49,030 --> 00:43:51,590 of factoring primes, is fundamentally broken 903 00:43:51,590 --> 00:43:54,789 by a new algorithm, or if the adversary has access 904 00:43:54,789 --> 00:43:57,730 to a physical side -channel attack, the randomization 905 00:43:57,730 --> 00:44:01,070 of the PRG does not save you. It is entirely 906 00:44:01,070 --> 00:44:03,949 conditional. And that deep, intrinsic connection 907 00:44:03,949 --> 00:44:06,610 between pseudo -randomness, cryptography, and 908 00:44:06,610 --> 00:44:09,909 complexity brings us to the most staggering plot 909 00:44:09,909 --> 00:44:13,480 twist in Watson's entire book. It explains exactly 910 00:44:13,480 --> 00:44:17,340 why P versus NP remains unsolved. It's the Rasmarov 911 00:44:17,340 --> 00:44:20,699 -Rudik natural proofs barrier. We discussed earlier 912 00:44:20,699 --> 00:44:23,780 how researchers failed to scale up the AC0 parity 913 00:44:23,780 --> 00:44:26,980 lower bounds to solve P versus NP. Alexander 914 00:44:26,980 --> 00:44:29,980 Razboff and Steven Rudig asked a profound meta 915 00:44:29,980 --> 00:44:33,179 question. Why did those techniques fail? What 916 00:44:33,179 --> 00:44:35,519 did they find? They analyzed the mathematical 917 00:44:35,519 --> 00:44:38,300 structure of all the successful circuit lower 918 00:44:38,300 --> 00:44:41,820 bound proofs in the history of the field, and 919 00:44:41,820 --> 00:44:44,750 they found a devastating commonality. they realized 920 00:44:44,750 --> 00:44:46,809 that all the mathematical techniques being used 921 00:44:46,809 --> 00:44:50,409 were what they termed natural proofs. What exactly 922 00:44:50,409 --> 00:44:53,150 constitutes a natural proof? To be classified 923 00:44:53,150 --> 00:44:55,849 as a natural proof, the mathematical technique 924 00:44:55,849 --> 00:44:58,909 must rely on finding a specific property of functions. 925 00:44:59,469 --> 00:45:01,750 This property must meet three strict criteria. 926 00:45:02,190 --> 00:45:04,909 Okay, lay them out. First, it must be constructive. 927 00:45:05,510 --> 00:45:07,690 An algorithm must be able to efficiently evaluate 928 00:45:07,690 --> 00:45:10,670 whether a function possesses this property. Second, 929 00:45:10,949 --> 00:45:13,539 it must be large. The property must hold true 930 00:45:13,539 --> 00:45:16,760 for a vast majority of completely random functions. 931 00:45:17,300 --> 00:45:20,579 Third, it must be useful. If a function possesses 932 00:45:20,579 --> 00:45:22,980 this property, it mathematically guarantees the 933 00:45:22,980 --> 00:45:25,719 function cannot be computed by a small, efficient 934 00:45:25,719 --> 00:45:27,980 circuit. That sounds like a perfectly logical 935 00:45:27,980 --> 00:45:30,219 battle plan. You find a property that almost 936 00:45:30,219 --> 00:45:32,960 all random functions have. You mathematically 937 00:45:32,960 --> 00:45:35,280 prove that small circuits are incapable of producing 938 00:45:35,280 --> 00:45:38,219 functions with that property. Then you show that 939 00:45:38,219 --> 00:45:41,179 your specific target function, like SAT, has 940 00:45:41,179 --> 00:45:44,559 the property. Boom. Lower bound proved. Small 941 00:45:44,559 --> 00:45:47,179 circuits can't compute SAT. P doesn't equal NP. 942 00:45:47,280 --> 00:45:49,760 What is the problem? The barrier is not a logical 943 00:45:49,760 --> 00:45:52,500 paradox, and natural proofs are not mathematically 944 00:45:52,500 --> 00:45:56,199 flawed. The Raspiro -Rudik barrier is a conditional 945 00:45:56,199 --> 00:46:00,250 limitation. The catastrophic twist is this. If 946 00:46:00,250 --> 00:46:02,130 you successfully find a natural property that 947 00:46:02,130 --> 00:46:04,590 works against general polynomial -sized circuits, 948 00:46:05,170 --> 00:46:07,050 you have essentially built a mathematical weapon 949 00:46:07,050 --> 00:46:09,690 that can look at any function and efficiently 950 00:46:09,690 --> 00:46:12,630 decide This function is too complex to be a small 951 00:46:12,630 --> 00:46:15,929 circuit. OK, I'm following. But recall our definition 952 00:46:15,929 --> 00:46:18,730 of a pseudo -random generator. The entire purpose 953 00:46:18,730 --> 00:46:21,110 of a PRG is to create a function that is computed 954 00:46:21,110 --> 00:46:24,230 by a small, highly efficient circuit, but which 955 00:46:24,230 --> 00:46:26,570 looks perfectly random to any efficient test. 956 00:46:26,789 --> 00:46:30,130 Oh no. Precisely. If a natural property exists 957 00:46:30,130 --> 00:46:32,630 for general circuits, it would act as an efficient 958 00:46:32,630 --> 00:46:35,710 test that recognizes random functions. Therefore, 959 00:46:36,110 --> 00:46:38,090 you could use the natural property to evaluate 960 00:46:38,090 --> 00:46:41,650 the output of a PRG. But the PRG is built by 961 00:46:41,650 --> 00:46:44,429 a small circuit. Right. So it cannot possess 962 00:46:44,429 --> 00:46:48,130 the useful property. But a truly random function 963 00:46:48,130 --> 00:46:51,210 does possess the large property. So the natural 964 00:46:51,210 --> 00:46:53,889 property would instantly distinguish the PRG's 965 00:46:53,889 --> 00:46:56,489 output from true randomness. It would break the 966 00:46:56,489 --> 00:46:59,929 pseudo -random generator entirely. Yes. A natural 967 00:46:59,929 --> 00:47:02,530 proof capable of solving P versus NP would, by 968 00:47:02,530 --> 00:47:06,190 its very mathematical structure, break all sufficiently 969 00:47:06,190 --> 00:47:10,489 strong PRGs. And since modern cryptography fundamentally 970 00:47:10,489 --> 00:47:14,429 relies on PRGs, we arrive at a staggering conditional 971 00:47:14,429 --> 00:47:19,090 reality. If cryptography is secure, natural proofs 972 00:47:19,090 --> 00:47:23,110 cannot solve P versus NP. The very lower bound 973 00:47:23,110 --> 00:47:26,130 we want to prove actively inhibits us from using 974 00:47:26,130 --> 00:47:28,090 natural mathematical properties to prove it. 975 00:47:28,289 --> 00:47:31,829 It is the ultimate cosmic catch -22. The tools 976 00:47:31,829 --> 00:47:34,769 we built to keep secrets are the exact mathematical 977 00:47:34,769 --> 00:47:36,909 structures blinding us from seeing the edges 978 00:47:36,909 --> 00:47:39,340 of computation. It's like trying to reach the 979 00:47:39,340 --> 00:47:41,880 moon by building a taller skyscraper. Exactly. 980 00:47:42,179 --> 00:47:44,320 The methods we used for shallow circuits, the 981 00:47:44,320 --> 00:47:47,400 skyscraper, are fundamentally the wrong physics 982 00:47:47,400 --> 00:47:51,019 for reaching the moon of general circuits. Natural 983 00:47:51,019 --> 00:47:53,840 proofs just scale up the skyscraper. We need 984 00:47:53,840 --> 00:47:56,199 a spaceship, and we currently don't know how 985 00:47:56,199 --> 00:47:59,099 to build one. But does this mean proving P versus 986 00:47:59,099 --> 00:48:02,420 NP is impossible? No. The barrier just means 987 00:48:02,420 --> 00:48:04,719 that all current natural routes are impossible. 988 00:48:05,159 --> 00:48:07,980 To prove P versus MP, we have to invent a mathematical 989 00:48:07,980 --> 00:48:12,099 property that is unnatural, one that is so incredibly 990 00:48:12,099 --> 00:48:15,780 rare it doesn't hold for random functions, or 991 00:48:15,780 --> 00:48:18,559 so computationally complex it cannot be efficiently 992 00:48:18,559 --> 00:48:22,019 evaluated, yet still manages to prove a lower 993 00:48:22,019 --> 00:48:25,340 bound. It basically forces the entire field of 994 00:48:25,340 --> 00:48:28,039 complexity theory to abandon decades of intuition 995 00:48:28,039 --> 00:48:31,340 and invent entirely new mathematics. It really 996 00:48:31,340 --> 00:48:35,119 does. What a phenomenal mind -bending journey. 997 00:48:35,329 --> 00:48:37,510 We've covered an incredible breadth of material 998 00:48:37,510 --> 00:48:40,349 from Thomas Watson's textbook today. We started 999 00:48:40,349 --> 00:48:42,510 at the bedrock, defining how memory and time 1000 00:48:42,510 --> 00:48:45,170 interact in the Word RAM model. We navigated 1001 00:48:45,170 --> 00:48:48,070 the time and space hierarchies, compressed memory 1002 00:48:48,070 --> 00:48:51,510 with the T log T theorem, and mapped out L, P, 1003 00:48:51,590 --> 00:48:54,989 P space, and XP. We really went through all of 1004 00:48:54,989 --> 00:48:57,289 it. We saw how reductions weave problems together, 1005 00:48:57,349 --> 00:49:00,869 leading to the verifiers of NP. We explored the 1006 00:49:00,869 --> 00:49:04,030 limitations of parallel processing in AC0 circuits. 1007 00:49:04,750 --> 00:49:07,130 We embraced the bounded chaos of coin tosses 1008 00:49:07,130 --> 00:49:10,150 in BPP and the error -correcting magic of the 1009 00:49:10,150 --> 00:49:13,389 PCP theorem. And ultimately, we collided with 1010 00:49:13,389 --> 00:49:16,389 the Razborov -Rudik natural proofs barrier. The 1011 00:49:16,389 --> 00:49:18,789 grand narrative arc of this field is honestly 1012 00:49:18,789 --> 00:49:22,070 poetry, the quest to strictly defined algorithmic 1013 00:49:22,070 --> 00:49:24,630 efficiency accidentally proved that the tools 1014 00:49:24,630 --> 00:49:27,349 we use to generate randomness and secure our 1015 00:49:27,349 --> 00:49:30,010 communications are fundamentally at odds with 1016 00:49:30,010 --> 00:49:32,349 our ability to mathematically prove the absolute 1017 00:49:32,349 --> 00:49:35,130 limits of computation. It leaves you with a lingering 1018 00:49:35,130 --> 00:49:37,670 provocative thought to mull over. If proving 1019 00:49:37,670 --> 00:49:40,309 that P does not equal NP inherently requires 1020 00:49:40,309 --> 00:49:43,110 us to invent an unnatural mathematical property, 1021 00:49:43,630 --> 00:49:45,769 something so rare it defies standard randomness 1022 00:49:45,769 --> 00:49:48,150 and so complex it cannot be efficiently evaluated, 1023 00:49:48,789 --> 00:49:51,130 what does that suggest about the intersection 1024 00:49:51,130 --> 00:49:53,989 of human intuition and mathematics? That's a 1025 00:49:53,989 --> 00:49:56,730 deep question. Human intuition naturally gravitates 1026 00:49:56,730 --> 00:49:59,690 toward constructive, large patterns. Are our 1027 00:49:59,690 --> 00:50:02,789 brains biologically wired to only see the skyscraper 1028 00:50:02,789 --> 00:50:05,269 when the universe's computational limits require 1029 00:50:05,269 --> 00:50:08,230 a spaceship? That is the philosophical frontier 1030 00:50:08,230 --> 00:50:11,579 of computer science. We know what is established, 1031 00:50:11,960 --> 00:50:14,079 and we know exactly where the open questions 1032 00:50:14,079 --> 00:50:17,780 lie. The rest requires a leap into the unnatural. 1033 00:50:18,400 --> 00:50:20,159 Thank you so much for joining us on this Deep 1034 00:50:20,159 --> 00:50:22,659 Dive. When you look at the abstract math of computer 1035 00:50:22,659 --> 00:50:25,099 science, remember that in the grand, intimidating 1036 00:50:25,099 --> 00:50:27,920 mansion of complexity theory, no matter how many 1037 00:50:27,920 --> 00:50:30,480 corridors you map out, there is always another 1038 00:50:30,480 --> 00:50:32,820 secret passage, and always another door waiting 1039 00:50:32,820 --> 00:50:35,019 to be opened. We'll catch you on the next Deep 1040 00:50:35,019 --> 00:50:35,219 Dive.