Chân trời mới của nghiên cứu thuật toán: chứng minh rằng “một ít bộ nhớ có thể mạnh hơn rất nhiều thời gian”

• Chứng minh mới do nhà khoa học máy tính lý thuyết của MIT Ryan Williams công bố cho thấy tài nguyên bộ nhớ có thể là tài nguyên tính toán mạnh hơn thời gian
• Công trình này phá vỡ 50 năm bế tắc về quan hệ độ phức tạp thời gian-không gian, đồng thời đưa ra cách biến đổi mọi thuật toán để dùng ít bộ nhớ hơn
• Trọng tâm của chứng minh là ý tưởng khái quát hóa mô phỏng tiết kiệm không gian để giảm mức sử dụng không gian của thuật toán xuống cỡ căn bậc hai của thời gian
• Nhờ đó, nghiên cứu đã tạo ra tiến triển trong việc chứng minh định lượng sự khác biệt giữa các lớp PSPACE và P, đồng thời mở ra khả năng dẫn tới những chứng minh có khoảng cách rộng hơn
• Các chuyên gia đánh giá thành tựu này là “một bước tiến đáng kinh ngạc và là điểm khởi đầu cho hành trình khám phá mới”, và cho rằng về sau kết quả này có thể trở thành đầu mối để giải các bài toán khó khác trong khoa học máy tính lý thuyết

---

One Small Step for Space, One Giant Leap for Complexity

Tổng quan về chứng minh mới của Ryan Williams

• Vào mùa hè năm 2024, Ryan Williams của MIT khi rà soát lại chứng minh của mình đã nhận ra rằng ý tưởng mà anh từng nghĩ là sai thực ra lại có hiệu lực
• Anh đề xuất một quy trình tổng quát để biến đổi mọi thuật toán thành dạng có thể chạy với ít bộ nhớ hơn
• Từ đó, anh chứng minh được rằng một số bài toán không thể được giải trong giới hạn thời gian nhất định

Thời gian và không gian: hai tài nguyên của tính toán

• Mọi thuật toán đều sử dụng thời gian và bộ nhớ (không gian)
• Trước đây, người ta thường cho rằng khi giải một bài toán cụ thể thì không gian tỉ lệ với thời gian
• Chứng minh của Williams thiết lập về mặt toán học rằng không gian có thể mạnh hơn thời gian

Khởi đầu và lịch sử của khoa học máy tính lý thuyết

• Juris Hartmanis và Richard Stearns đã đặt ra định nghĩa về độ phức tạp thời gian/không gian vào thập niên 1960
• Họ đặt nền móng cho việc phân loại các bài toán thành các lớp độ phức tạp dựa trên tài nguyên cần thiết để giải chúng
• P là lớp các bài toán có thể giải trong thời gian hợp lý, còn PSPACE là lớp các bài toán có thể giải với lượng bộ nhớ hợp lý

Tiến triển đầu tiên: kỹ thuật mô phỏng năm 1975

• Hopcroft, Paul, Valiant đã phát triển một quy trình mô phỏng phổ quát có thể biến đổi mọi thuật toán để dùng ít không gian hơn một chút
• Đây là bước đi đầu tiên giúp làm sáng tỏ mối liên hệ giữa thời gian và không gian, nhưng sau đó đã chạm tới giới hạn
• Người ta cho rằng không thể tiến thêm vì giả định rằng dữ liệu không thể đồng thời chiếm cùng một không gian

Bước ngoặt: Squishy Pebbles

• Năm 2010, nhà lý thuyết độ phức tạp tiên phong Stephen Cook và các cộng sự đã đưa ra bài toán đánh giá cây - Pebbles and Branching Programs for Tree Evaluation, rồi chứng minh rằng bài toán này không thể được giải bởi các thuật toán có ngân sách không gian dưới một ngưỡng nhất định
  • Nhưng vẫn có một lỗ hổng. Chứng minh đó dựa trên cùng kiểu giả định có vẻ hiển nhiên như những gì Paul và cộng sự đã đưa ra từ nhiều thập niên trước
  • Cụ thể là thuật toán không thể lưu dữ liệu mới vào một vùng nhớ đã đầy sẵn
  • Trong hơn 10 năm, các nhà lý thuyết độ phức tạp đã cố gắng vá lỗ hổng đó
• James Cook, con trai của Stephen Cook, cùng Ian Mertz đã công bố vào năm 2023 một thuật toán cho bài toán đánh giá cây phá vỡ giả định cũ: Tree Evaluation Is in Space 𝑂 (log 𝑛 · log log 𝑛)
• Họ đề xuất một mô hình biểu diễn mới trong đó dữ liệu trong bộ nhớ có thể chồng lấp nhau về mặt vật lý
• Cách tiếp cận này trở thành chìa khóa để vượt qua các giới hạn mô phỏng trước đây

Bước nhảy quyết định của Williams

• Sau khi biết đến kỹ thuật Cook-Mertz qua bài trình bày của các sinh viên, Williams đã nảy ra ý tưởng áp dụng nó vào mô phỏng phổ quát
• Phép mô phỏng mới có thể giảm nhu cầu không gian của thuật toán xuống mức căn bậc hai của thời gian
• Tháng 2 năm 2025, anh đăng bài báo hoàn chỉnh lên arXiv và nhận được sự tán dương lớn từ giới học thuật

Ý nghĩa của kết quả này

• Chứng minh này chưa trực tiếp chứng minh PSPACE > P, nhưng là thành tựu mang tính quyết định đã tạo ra một “khe hở” để tiến theo hướng đó
• Nếu sau này có thể áp dụng lặp lại quy trình này để tạo ra khoảng cách lớn hơn, thì có thể tiến gần tới việc giải bài toán P vs PSPACE
• Đây có thể là manh mối đầu tiên để giải một trong những bài toán khó lâu đời nhất của khoa học máy tính

Kết thúc đọng lại dư âm

• Williams hồi tưởng về kết quả này như sau:
  “Tôi đã không chứng minh được điều mà mình thực sự muốn chứng minh, nhưng rốt cuộc thứ tôi chứng minh được còn tuyệt vời hơn cả điều mình mong muốn.”

[nunojay]

....Hả?

[GN⁺]

Ý kiến trên Hacker News

• Nói ngắn gọn bỏ qua phần mơ hồ, một máy Turing nhiều băng chạy trong thời gian t có thể được mô phỏng bằng cách dùng không gian O(sqrt(t log t)) (thường thì thời gian sẽ lâu hơn t) Simulating Time With Square-Root Space
  • Điều đáng tiếc là các bài của Quanta hay trộn quá nhiều cách diễn đạt mang tính thi vị hoặc cường điệu vào toán học nên dễ gây hiểu nhầm. Bài Quanta nói rằng “một số tác vụ cần lượng không gian tỷ lệ với thời gian chạy”, nhưng chỉ nhìn vào complexity hierarchy thôi cũng không rút ra trực giác tổng quát như vậy. Không thể lấy câu chuyện chỉ đúng với “một số thuật toán” để xây thành trực giác chung
  • Có phải vì họ quá chiều độc giả không, nhưng việc Quanta giải thích lớp độ phức tạp P chỉ là “mọi bài toán có thể giải trong thời gian hợp lý” mà không hề dùng chính thuật ngữ polynomial khiến tôi thấy hơi xúc phạm
• Trong “Camel Book” mang đậm triết lý Perl có một câu thế này: “Thiếu bộ nhớ thì có thể đi mua, còn thiếu thời gian thì chẳng có cách nào cả”. Tôi yêu cuốn sách đó đơn giản vì nó rất vui
  • Tôi nghĩ câu này cũng có hai mặt. Chương trình cần nhiều hơn lượng bộ nhớ máy tính đang có thì không thể chạy ngay được, còn nếu chỉ tốn lâu thì ít nhất vẫn chạy được, nên thời gian rốt cuộc cũng là một tài nguyên quan trọng
• Chiến thắng của các lookup table lưu sẵn giá trị đã tính trước. Trước đây tôi từng nghĩ nếu có thể lưu toàn bộ phép tính ở một nơi trung tâm đến mức gần như không cần bộ xử lý thì tốc độ xử lý sẽ cách mạng hóa được mọi thứ (thực ra vẫn còn bài toán khó riêng là tìm kiếm nhanh)
  • Hồi mới bắt đầu làm việc về hệ thống lưu trữ, tôi từng đề xuất ý tưởng tính trước rồi lưu toàn bộ các khối 4KB, sau đó bị chỉ ra rằng số khối 4KB duy nhất còn nhiều hơn số nguyên tử trong vũ trụ, và tôi vẫn nhớ cảm giác choáng váng lúc đó
  • Thuật toán HashLife làm điều gì đó tương tự theo cách Turing-đầy đủ trong Conway's Game of Life. Tôi thấy thật kỳ thú khi ngay cả với những trạng thái cực kỳ phức tạp và đa dạng, vẫn có thể tính trước trạng thái tương lai theo kiểu nhảy cóc
  • Đùa rằng cũng chẳng có vấn đề gì với ý tưởng cache luôn cả chính việc retrieval (tra cứu) của lookup
  • Điều này trên thực tế đã được triển khai dưới dạng cache ở cấp cộng đồng, tức mô hình phân phối phần mềm đã được precompile. Cả rào cản truyền thống là phải từ bỏ tính năng ngôn ngữ vì không biên dịch hiệu quả được cũng có thể vượt qua nhờ biên dịch song song trên cloud và cache toàn cầu. Chỉ cần biên dịch một lần khi phát hành là mọi người cùng dùng được
  • Tiếp nối ý “nếu lưu mọi phép tính ở trung tâm thì có lẽ không cần bộ xử lý”, tôi còn nghĩ tới chuyện memoize luôn cả lịch sử tra cứu
• Vì văn phong Quanta quá thi vị nên khó hiểu liệu nghiên cứu này có thực sự áp dụng được cho máy tính thực tế hay chỉ là một kịch bản thuần lý thuyết. Tôi muốn biết có phải ý của nó là dùng nhiều bộ nhớ hơn để đổi lấy máy tính chậm đi hay không
• Tôi đã làm lập trình đồ họa raster rất lâu nên việc tận dụng lookup table gần như đã thành phản xạ. Gần đây tôi phát triển một công cụ server cho phép đưa sẵn nhiều hình vào DB rồi mỗi lần query sẽ dùng kết quả tối ưu hóa sẵn. Đây là một mẫu hình không phức tạp mà rất trực quan. Tôi chẳng hề được giáo sư MIT nào dạy riêng cả, chỉ là cách làm tự mình rèn ra, nên khi thấy có bằng chứng toán học biện minh cho nó thì rất vui. Tôi cũng nghĩ nhiều bí quyết thuật toán thực ra thường bắt nguồn từ kinh nghiệm của người làm thực tế (ví dụ: thuật toán winding number)
  • Những kết quả tối ưu hóa game mà tôi đạt được dạo này đều đến từ việc xử lý lookup table theo ngữ cảnh. Lookup table không nhất thiết phải là mảng tĩnh; dữ liệu thay đổi nhẹ theo thời gian cũng có thể khai thác theo cách tương tự. Điều đó khiến tôi bắt đầu nhìn sang hướng đẩy việc xử lý lên GPU, và có vẻ rất hiệu quả khi thay vì các bảng được tạo tĩnh lúc compile hoặc runtime, ta chỉ cập nhật một phần trong runtime rồi chuyển chúng sang GPU như texture. Ranh giới của việc cái gì được gọi là lookup table ngày càng mờ đi
• Tôi có trực giác rằng không gian (bộ nhớ) có thể biểu diễn lượng kết quả lớn hơn rất nhiều so với thời gian. Với băng có độ dài n thì bạn có thể ghi trong O(n) thời gian, nhưng nếu đó là băng nhị phân thì tồn tại 2^n cấu hình cho độ dài n. Nếu dùng không gian đúng cách thì nó mang lại sức biểu đạt lớn hơn thời gian rất nhiều
  • Trực giác của tôi là: một ô có thể lưu kết quả trung gian của hàng trăm lần tính toán. Nếu không thể lưu kết quả trung gian mà cứ phải tính lại cùng một thứ hết lần này đến lần khác thì hiệu quả sẽ giảm rất mạnh. Tình huống cache hit rate bằng 0% là rất hiếm; phần lớn trường hợp đều có thể tối ưu nhờ tận dụng không gian. Ngược lại, khó mà dùng một đơn vị thời gian để thay thế cho hàng trăm ô nhớ, và với kiến trúc tính toán hiện nay thì SIMD vô hạn là bất khả thi
  • Giả định random access O(1) đối với bộ nhớ bị coi là quá hiển nhiên, nhưng trong thực tế khi máy tính lớn lên thì chi phí truy cập có thể tăng đến O(n^(1/3)). Có thể cảm nhận điều này rất rõ ở data center. Tôi nhớ đó là một mô hình khác chứ không phải UMA
  • Vì P ≠ PSPACE vẫn chưa được chứng minh, đây là lĩnh vực mà việc chứng minh bằng toán học khó hơn nhiều so với trực giác
  • Mặt khác, điều đó đúng nhưng với những bài toán khó song song hóa (ví dụ: alternating machine PTIME=PSPACE), không gian có thể cũng không mang lại lợi ích lớn. Trong bài báo, bước nhảy từ t/log t lên sqrt(t log t) là đột phá, nhưng hẳn vẫn sẽ có những giới hạn bản chất không thể vượt qua ngay cả với song song hóa vô hạn
  • Trong thực tế thì còn tùy tính chất công việc. Khi truy cập storage chậm hơn rất nhiều so với phép gán, đôi khi tính lại còn nhanh hơn
• “Quan hệ đánh đổi” giữa thời gian và không gian có thể được giải thích là khi giới hạn một tài nguyên thì không thể mặc nhiên đạt được giá trị tối ưu của tài nguyên kia. Ví dụ với thuật toán sắp xếp, nếu có ba ràng buộc là thời gian/không gian/tính ổn định, thì khi buộc phải thỏa thêm tính ổn định, hiệu quả về thời gian hoặc không gian có thể tệ đi. Cho đến nay vẫn chưa có stable sort nào vừa nhanh vừa ít tốn bộ nhớ như các thuật toán sắp xếp không ổn định
• Cá nhân tôi thích văn phong bài viết của Quanta Magazine. Nó giúp mở rộng tầm nhìn không chỉ cho các nhà khoa học máy tính mà cả những người bình thường quan tâm tới lĩnh vực liên quan. Góc nhìn toàn cảnh và cách giải thích gần gũi là thứ khơi ra những góc nhìn và ý tưởng mới
• Chia sẻ link tới bài nói chuyện và bài báo của Ryan Williams
• Nếu một máy Turing single-tape nhận đầu vào là số nhị phân N và muốn ghi N ký tự 1 ở phía bên phải của tape, thì có vẻ nó cần N ô không gian trong thời gian N. Vậy làm sao có thể mô phỏng việc này với ít hơn N không gian? Vì máy Turing không thể nhảy đến vị trí bất kỳ trên tape, nên tôi cũng tò mò điều này liên hệ thế nào với máy tính thực tế
  • Máy Turing nhiều băng nhanh hơn máy một băng rất nhiều, và “không gian” ở đây là vùng làm việc tạm thời không tính phần đầu vào/đầu ra
  • Bài báo chủ yếu xét các bài toán quyết định, tức chỉ cần đầu ra 1 bit. Nếu đầu ra dài N bit thì về bản chất nó tương đương với việc ghép N bài toán quyết định lại với nhau