Ryan Williams introduces the three-sum problem, explaining how to achieve sub-quadratic time algorithms using group-based finger search and pre-processing. He relates this to fine-grained complexity research, which focuses on proving lower bounds for problems like three-sum. The discussion covers advanced algorithms that use group decomposition and data structures to speed up finger moves, achieving sub-quadratic time. Key concepts include finger search, contiguous pre-processing, and linear decision trees.
Ryan Williams giới thiệu bài toán tổng ba, giải thích cách đạt được thuật toán thời gian dưới bậc hai bằng cách sử dụng tìm kiếm ngón tay dựa trên nhóm và tiền xử lý. Ông liên hệ điều này với nghiên cứu độ phức tạp tinh tế, tập trung vào việc chứng minh cận dưới cho các bài toán như tổng ba. Thảo luận bao gồm các thuật toán nâng cao sử dụng phân rã nhóm và cấu trúc dữ liệu để tăng tốc các bước di chuyển ngón tay, đạt thời gian dưới bậc hai. Các khái niệm chính bao gồm tìm kiếm ngón tay, tiền xử lý liên tục và cây quyết định tuyến tính.
Hypotheses which are at the edge of our understanding can be enlightening.
Những giả thuyết nằm ở rìa hiểu biết của chúng ta có thể mang tính khai sáng.
- This is Ryan Williams.
- Đây là Ryan Williams.
He's a professor at MIT who won the Gödel Prize for theoretical computer science, and I started by asking him a LeetCode question.
Anh ấy là giáo sư tại MIT, người đã giành giải Gödel cho khoa học máy tính lý thuyết, và tôi bắt đầu bằng cách hỏi anh ấy một câu hỏi LeetCode.
So, the question is three-sum.
Vậy, câu hỏi là three-sum.
Can you do better than n squared for this?
Liệu bạn có thể làm tốt hơn n bình phương cho bài toán này không?
- Yeah, you actually can do better than n squared, and this is um not at all obvious.
- Ừ, bạn thực sự có thể làm tốt hơn n bình phương, và điều này không hề hiển nhiên.
- He also had contrarian takes on popular hypotheses.
- Anh ấy cũng có những quan điểm trái chiều về các giả thuyết phổ biến.
- I think I'm on the record as not believing this hypothesis.
- Tôi nghĩ tôi đã từng nói rằng tôi không tin vào giả thuyết này.
We really don't understand polynomial time computation as deeply as we think we do.
Chúng ta thực sự không hiểu sâu về tính toán thời gian đa thức như chúng ta nghĩ.
- All right, I want to start by asking you the most popular LeetCode question.
- Được rồi, tôi muốn bắt đầu bằng cách hỏi bạn câu hỏi LeetCode phổ biến nhất.
So, the question is three-sum.
Vậy, câu hỏi là three-sum.
Given a list of numbers, and we want to find three numbers such that they sum to zero.
Cho một danh sách các số, và chúng ta muốn tìm ba số sao cho tổng của chúng bằng 0.
- Yes.
- Vâng.
- And so, what are your thoughts on the brute-force solution for this?
- Vậy, bạn nghĩ gì về giải pháp brute-force cho bài toán này?
We can start there.
Chúng ta có thể bắt đầu từ đó.
- So, the obvious brute-force solution takes if you've got n numbers n cubed time.
- Vậy, giải pháp brute-force hiển nhiên mất thời gian n mũ ba nếu bạn có n số.
Just try all the triples of numbers, sum them up, see if they sum to zero.
Chỉ cần thử tất cả các bộ ba số, cộng chúng lại, xem tổng có bằng 0 không.
There is a faster uh solution.
Có một giải pháp nhanh hơn.
So, one way to get an order n squared time algorithm for three-sum is to first start by sorting the numbers.
Vậy, một cách để có thuật toán thời gian n bình phương cho three-sum là đầu tiên sắp xếp các số.
And then, you go through the numbers one by one.
Và sau đó, bạn duyệt qua từng số một.
Say like, you're looking at a number A.
Giả sử, bạn đang xem xét một số A.
And you want to know, is there a B and a C in the rest of the list um whose sum with A is going to be zero?
Và bạn muốn biết, liệu có B và C trong phần còn lại của danh sách mà tổng của chúng với A bằng 0 không?
Okay, so, the way this works is after you sort the numbers, you do what's called a finger search.
Được rồi, cách hoạt động là sau khi bạn sắp xếp các số, bạn thực hiện cái gọi là tìm kiếm bằng ngón tay.
So, you put um the finger from your left hand on the minimum element and finger from your right hand on the maximum element.
Vậy, bạn đặt ngón tay trái lên phần tử nhỏ nhất và ngón tay phải lên phần tử lớn nhất.
So you start there.
Vậy bạn bắt đầu từ đó.
And you check like, okay, are these my B and C?
Và bạn kiểm tra, okay, đây có phải là B và C của tôi không?
Right?
Phải không?
So you add them min and max and check if adding that with A gets you zero.
Vậy bạn cộng min và max và kiểm tra xem cộng với A có được 0 không.
Okay?
Được chứ?
And um if you're lucky, okay, then you're done, but typically you're not lucky.
Và nếu bạn may mắn, okay, bạn xong rồi, nhưng thường thì bạn không may mắn.
And so this sum of the min and the max is either um larger than your target value minus A or it's smaller.
Và tổng của min và max này hoặc là lớn hơn giá trị mục tiêu trừ A hoặc là nhỏ hơn.
Okay?
Được chứ?
If it's larger, then you need to decrease the larger number.
Nếu nó lớn hơn, thì bạn cần giảm số lớn hơn.
So you take your right finger, which is sitting on the maximum element, and you move it to the left one slot.
Vậy bạn lấy ngón tay phải, đang ở phần tử lớn nhất, và di chuyển nó sang trái một ô.
Okay?
Được chứ?
So you decrease the larger one.
Vậy bạn giảm số lớn hơn.
All right?
Đúng không?
If the sum is smaller than your target, you need to take the smaller number and make it a little bit bigger.
Nếu tổng nhỏ hơn mục tiêu của bạn, bạn cần lấy số nhỏ hơn và làm nó lớn hơn một chút.
So you move the you move your left finger sitting on the minimum over one slot.
Vậy bạn di chuyển ngón tay trái đang ở phần tử nhỏ nhất sang phải một ô.
Okay?
Được chứ?
And you keep doing this.
Và bạn tiếp tục làm như vậy.
You keep checking whether, you know, your left finger and right finger are pointing at a solution.
Bạn liên tục kiểm tra xem, bạn biết đấy, ngón tay trái và ngón tay phải của bạn có đang chỉ vào một giải pháp không.
And if they aren't, then you adjust it.
Và nếu không, thì bạn điều chỉnh nó.
If they do, they ever do sum up to exactly what you want, you're done.
Nếu chúng có tổng đúng bằng những gì bạn muốn, bạn xong.
And so after each comparison like this, right?
Và sau mỗi lần so sánh như vậy, phải không?
One of your fingers moved.
Một trong các ngón tay của bạn đã di chuyển.
Okay?
Được chứ?
If the fingers ever cross, then you don't have a solution.
Nếu các ngón tay chéo nhau, thì bạn không có giải pháp.
Like there's just there just can't be a solution.
Kiểu như không thể có giải pháp.
And so the number of times you move, you know, your fingers in total is like N.
Và số lần bạn di chuyển ngón tay tổng cộng là N.
So you have a order N solution for finding that extra pair.
Vậy bạn có giải pháp O(N) để tìm cặp đó.
And you do this for each of the numbers A.
Và bạn làm điều này cho mỗi số trong A.
Okay?
Được chứ?
So then you get a order N squared uh solution overall.
Vậy thì bạn có giải pháp O(N bình phương) tổng thể.
You do it N times.
Bạn thực hiện nó N lần.
Each finger search uh takes order N time.
Mỗi lần tìm kiếm bằng ngón tay mất O(N) thời gian.
- And that is the popular solution.
- Và đó là giải pháp phổ biến.
think.
Hãy suy nghĩ.
- solution, yes.
- giải pháp, vâng.
- of people know when we're in these algorithmic LeetCode interviews.
- nhiều người biết khi chúng ta ở trong các cuộc phỏng vấn thuật toán LeetCode này.
And I know a lot of your research is kind of about pushing lower bounds, so maybe we can start that conversation off by can you do better than n squared for this?
Và tôi biết nhiều nghiên cứu của bạn là về việc đẩy giới hạn dưới, vậy có lẽ chúng ta có thể bắt đầu cuộc trò chuyện đó bằng câu hỏi: bạn có thể làm tốt hơn n bình phương cho bài toán này không?
- Yeah, you actually can do better than n squared.
- Vâng, thực ra bạn có thể làm tốt hơn n bình phương.
And this is um uh not at all obvious.
Và điều này hoàn toàn không hiển nhiên.
In fact, it stems from um taking this finger search idea and pushing it in a different direction.
Thực tế, nó bắt nguồn từ việc lấy ý tưởng tìm kiếm bằng ngón tay và đẩy nó theo một hướng khác.
So, what you do is you take your sorted list, okay, and you break uh the sorted list up into little groups of contiguous elements.
Vậy, bạn lấy danh sách đã sắp xếp của mình, và bạn chia danh sách đã sắp xếp thành các nhóm nhỏ gồm các phần tử liên tiếp.
So, let's say your little group is like log n size or square root log n.
Giả sử, nhóm nhỏ của bạn có kích thước log n hoặc căn bậc hai của log n.
It's like a really small little group, okay?
Nó giống như một nhóm nhỏ rất nhỏ, được chứ?
So, you've got either n over log n groups total or n over square root log n groups total depending on how you break up your groups.
Vậy, bạn có tổng cộng n/log n nhóm hoặc n/căn(log n) nhóm tùy thuộc vào cách bạn chia nhóm.
And then the idea is you're going to perform the same kind of finger search, but you're going to set things up so that you're comparing two pairs of groups.
Và sau đó ý tưởng là bạn sẽ thực hiện cùng một loại tìm kiếm bằng ngón tay, nhưng bạn sẽ sắp xếp mọi thứ để so sánh hai cặp nhóm.
Your finger's always pointing at an entire group.
Ngón tay của bạn luôn trỏ vào toàn bộ một nhóm.
So, like the left hand and right hand are pointing at two groups and you want to know if there's a three sum solution in that group.
Vậy, tay trái và tay phải đang trỏ vào hai nhóm và bạn muốn biết liệu có giải pháp three-sum trong nhóm đó không.
And you can set up a kind of fast data structure to check a small group, okay?
Và bạn có thể thiết lập một loại cấu trúc dữ liệu nhanh để kiểm tra một nhóm nhỏ, được chứ?
And this data structure will take much less than um the number of elements in the two groups squared.
Và cấu trúc dữ liệu này sẽ mất ít thời gian hơn nhiều so với bình phương số phần tử trong hai nhóm.
So, you set up some kind of fancy data structure.
Vậy, bạn thiết lập một loại cấu trúc dữ liệu cầu kỳ nào đó.
And because you set your group size so small, it's like a pre-processing that you do over all the possible inputs you could send from a pair of groups.
Và bởi vì bạn đặt kích thước nhóm rất nhỏ, nó giống như một bước tiền xử lý mà bạn thực hiện trên tất cả các đầu vào có thể từ một cặp nhóm.
And so, you have some data structure and it will, you know, let's say it takes you n to the 1.5 time to prepare this data structure, this fancy data structure.
Và vậy, bạn có một cấu trúc dữ liệu nào đó và nó sẽ, bạn biết đấy, giả sử nó mất n mũ 1.5 thời gian để chuẩn bị cấu trúc dữ liệu cầu kỳ này.
But now, when you're looking at a pair of groups, you can look at the answer much faster than what finger search would have taken.
Nhưng bây giờ, khi bạn xem xét một cặp nhóm, bạn có thể tìm câu trả lời nhanh hơn nhiều so với tìm kiếm bằng ngón tay.
I guess finger search through like a group of length G and another group of length G would take about order
Tôi đoán tìm kiếm bằng ngón tay qua một nhóm có độ dài G và một nhóm khác có độ dài G sẽ mất khoảng O(G) thời gian,
G time, and you can do actually do faster by this kind of look up.
và bạn thực sự có thể làm nhanh hơn bằng cách tra cứu này.
This kind of table look up.
Loại tra cứu bảng này.
I think it is kind of like you take uh this list of length N and you uh kind of shrink it into like N over num uh N over N over group size uh number of things.
Tôi nghĩ nó giống như bạn lấy danh sách độ dài N này và bạn thu nhỏ nó thành N/(kích thước nhóm) số lượng đối tượng.
And these are more complicated objects.
Và đây là những đối tượng phức tạp hơn.
And then you do And now like you're trying to you're trying to speed up like the check over these like small uh complicated objects.
Và sau đó bạn cố gắng tăng tốc việc kiểm tra trên các đối tượng nhỏ phức tạp này.
For like, should I move my finger to the right?
Ví dụ, tôi có nên di chuyển ngón tay sang phải không?
Like, is there nothing in this group?
Có gì trong nhóm này không?
Would finger search just go straight through this group or not?
Liệu tìm kiếm bằng ngón tay có đi thẳng qua nhóm này hay không?
Is basically what you're asking.
Về cơ bản đó là câu hỏi bạn đang đặt ra.
- So, the unit that you're operating on is not a single integer, it's a a group.
- Vậy, đơn vị bạn đang thao tác không phải là một số nguyên đơn lẻ, mà là một nhóm.
- Yeah, it's like a group of them.
- Đúng, nó giống như một nhóm các số.
So, you use some kind of table look up.
Vậy, bạn sử dụng một loại tra cứu bảng nào đó.
Uh And so, well, it's it's it's much fancier than a table look up, actually.
Ừ, và thực ra nó còn cầu kỳ hơn nhiều so với tra cứu bảng.
It's It goes through some other model called the linear decision tree model.
Nó đi qua một mô hình khác gọi là mô hình cây quyết định tuyến tính.
Like, so it's like in some weird model where you can actually get a faster three some solution.
Giống như, trong một mô hình kỳ lạ nào đó, bạn thực sự có thể có giải pháp three-sum nhanh hơn.
You can get a N to the 1.5 solution.
Bạn có thể có giải pháp N mũ 1.5.
And there's It's a really interesting and sophisticated solution, but what I want to emphasize is it starts from the finger search solution.
Và đó là một giải pháp thực sự thú vị và tinh vi, nhưng điều tôi muốn nhấn mạnh là nó bắt đầu từ giải pháp tìm kiếm bằng ngón tay.
And sort of like figuring out how to like
Và đại loại như tìm ra cách để
process finger moves faster.
xử lý các chuyển động ngón tay nhanh hơn.
Uh sort of do pre-processing so that finger moves can go faster.
Ừ, thực hiện tiền xử lý để các chuyển động ngón tay có thể nhanh hơn.
- Yeah, I saw the time complexity this.
- Vâng, tôi đã thấy độ phức tạp thời gian này.
It's N squared divided by log N divided by log N all raised to the 2/3.
Đó là N bình phương chia cho log N chia cho log N tất cả mũ 2/3.
What Is there any intuition behind I mean, that's just crazy.
Có trực giác nào đằng sau điều đó không? Ý tôi là, điều đó thật điên rồ.
- So, there are several algorithms of this kind, and they all work by doing some modification on what I was talking about because you can sort of reduce to a different model.
- Vì vậy, có một số thuật toán loại này, và tất cả chúng đều hoạt động bằng cách thực hiện một số sửa đổi trên những gì tôi đã nói vì bạn có thể giảm xuống một mô hình khác.
Like a like a a different kind of look up table, a different kind of set of tricks.
Giống như một loại bảng tra cứu khác, một loại bộ thủ thuật khác.
And you know, maybe there is some savings you can do here and there by sort of compressing things a little differently.
Và bạn biết đấy, có thể có một số tiết kiệm bạn có thể thực hiện ở đây và ở đó bằng cách nén mọi thứ một chút khác đi.
Um so, that yeah, there are several algorithms that beat the n squared running time bound, and they all, to my knowledge, kind of work in a similar type of way.
Ừm, vâng, có một số thuật toán vượt qua ràng buộc thời gian chạy n bình phương, và theo hiểu biết của tôi, tất cả chúng đều hoạt động theo một cách tương tự.
Like they they're they're taking this n squared time algorithm and finding little ways to like pre-process
Giống như chúng đang lấy thuật toán thời gian n bình phương này và tìm ra những cách nhỏ để tiền xử lý
and then optimize like based on the pre-processing.
Và sau đó tối ưu hóa dựa trên tiền xử lý.
Like make finger searches faster and things like that.
Giống như làm cho tìm kiếm ngón tay nhanh hơn và những thứ tương tự.
Sort of yeah.
Đại loại vậy.
- A lot of your research is on this topic of fine-grained complexity or kind of lowering lower bounds.
- Rất nhiều nghiên cứu của bạn về chủ đề độ phức tạp chi tiết hoặc loại hạ thấp cận dưới.
So, um maybe you can explain what is fine-grained - Lowering lower bounds, I like that.
Vì vậy, ừm có lẽ bạn có thể giải thích độ phức tạp chi tiết là gì? - Hạ thấp cận dưới, tôi thích điều đó.