OpenAI và Anthropic cùng bác bỏ giả thuyết ETH ngày 26/10 bằng thuật toán đếm 3-SAT dưới thời gian mũ

Ngày 26/10/2026, OpenAI và Anthropic cùng công bố tuyên bố bác bỏ một giả thuyết nền tảng của khoa học máy tính từ năm 1999, kèm bản kiểm tra bằng máy Lean, nhưng tới 03/11/2026 vẫn chưa có kết luận rà soát độc lập hoàn chỉnh nào được báo cáo. ETH ở đây là Exponential Time Hypothesis, anh em đừng nhầm với đồng Ethereum.

Tóm tắt nhanh: hai lab tuyên bố thuật toán đếm 3-SAT dưới thời gian mũ kèm bản Lean đã chạy qua, con người vẫn đang rà soát phát biểu formal tới 03/11/2026.

ETH là gì và bài toán đếm 3-SAT hoạt động ra sao

ETH là cái neo cho cả một vùng lý thuyết.

Giả thuyết từ năm 1999 của Impagliazzo và Paturi

ETH, theo Fortnow và OpenAI, được đề xuất năm 1999 bởi Russell Impagliazzo và Ramamohan Paturi, và nói 3-SAT không thể giải nhanh hơn mức mũ một cách căn bản, thời gian chạy luôn chứa một tỉ lệ cố định của số biến trong số mũ, và tỉ lệ đó không thể tiến về 0 khi bài toán lớn dần.

Ví dụ công tắc bật tắt cho 3-SAT và đếm 3-SAT

Anh em hình dung một bảng có n công tắc, mỗi công tắc chỉ bật hoặc tắt, kèm danh sách dài các điều kiện nhỏ, mỗi điều kiện chỉ nhắc tới tối đa 3 công tắc, ví dụ A bật, hoặc B tắt, hoặc C bật, rồi 3-SAT hỏi có cách bật tắt nào làm mọi điều kiện cùng đúng hay không, trong khi đếm 3-SAT hỏi có tất cả bao nhiêu cách như vậy. Cách thô nhất là thử hết 2^n cách, và đếm xong thì biết ngay có nghiệm hay không, vì số đếm lớn hơn 0 nghĩa là có nghiệm, nên thuật toán đếm dưới mũ tự động cho ra thuật toán quyết định dưới mũ.

Vì sao giới chuyên môn xôn xao dù bài toán nghe rất trừu tượng

ETH là cái neo mà hàng trăm bài báo dùng để suy ra một bài toán không thể giải nhanh hơn mức nào đó, nên nếu neo đó gãy thì các kết quả dựa vào nó phải xem lại nền móng, dù các kết luận đó chưa chắc đã sai.

Hai lab tuyên bố gì, ngày nào, giống nhau và khác nhau ở đâu

Mình thấy điểm đáng để ý ở đây là hai lab tự báo cùng một ngày tìm ra kết quả rồi công bố cùng một tối.

Timeline từ ngày tìm ra tới ngày công bố

Ngày 16/10/2026, theo lời kể của mỗi lab, model nội bộ của OpenAI tìm ra bản bác bỏ ETH bằng ngôn ngữ tự nhiên, còn model Claude nghiên cứu nội bộ của Anthropic tìm ra thuật toán lõi, và đây là ngày hai lab tự báo, chưa có bên độc lập nào xác nhận. Ngày 17/10/2026, theo OpenAI, bản bác bỏ được formal hóa bằng Lean, bản thảo sửa ngày 25/10/2026, tên bài là The Exponential Time Hypothesis is False, tác giả ghi là OpenAI, dài 67 trang, là kết quả số 378 trong repo openai/math.

Ngày 26/10/2026, OpenAI công bố 3 kết quả trên blog chính thức, gồm kết quả ETH cùng chứng minh local smoothing trong mọi chiều và chứng minh tồn tại cho QCD và hoàn thiện mô hình chuẩn, kèm cam kết 5 triệu USD cho sáng kiến Simons Foundation. File ETH lên repo lúc 16:52 giờ miền Đông Mỹ theo nguồn thứ cấp đối chiếu log commit, và cùng tối đó file Anthropic lên repo anthropics/formal-math lúc 23:07 giờ miền Đông Mỹ cũng theo nguồn thứ cấp này.

Bài báo Anthropic tên A 2^o(n) Time Algorithm for 3-SAT, tác giả ghi là Claude (Anthropic), dài 49 trang, đề ngày 26/10/2026, lên GitHub và Hexagon ngày 27/10/2026 giờ UTC với mã 2610.00577v1, người nộp là Jelani Nelson thay mặt Anthropic, bài báo mang nhãn chủ yếu do AI tạo ra, chỉ một phần được con người kiểm tra và hiểu, và Anthropic nói độc lập và đồng thời trong mục Provenance.

Bound của OpenAI trong bản thảo và trong bản Lean

Anh em cứ nhớ n là số biến, m là số mệnh đề, k là độ rộng mệnh đề, rồi thuật toán tất định của OpenAI đếm chính xác số cách gán thỏa mãn của công thức k-CNF bất kỳ, với thời gian ở Abstract là (n+m)^O_k(1) nhân 2^(n/(logn)^(1/2+o(1))). Định lý 1.1 nêu dạng (n+m)^O_k(1) 2^O_k(nloglogn/sqrt(logn)), kèm hệ quả bác bỏ ETH, SETH, Gap-ETH và NSETH. Khi m không vượt quá Dn với D cố định, Định lý 1.1 còn cải thiện thành (n+m)^O_{k,D}(1) 2^O_{k,D}(n/sqrt(logn)).

Bound của Anthropic và dấu vết model tự tìm ra

Chỗ Anthropic thì bound chính là thuật toán tất định giải 3-SAT trên n biến trong thời gian 2^o(n). Thực ra nó giải bài toán đếm #3-SAT trong thời gian 2^O(nloglogn/sqrt(logn)), và định lý chính bao quát đếm k-CNF với dạng đầy đủ là 2^O(min{knloglogn/sqrt(logn),km/sqrt(logm)}). Theo nguồn thứ cấp, kỹ thuật là viết lại việc đếm 3-SAT thành co rút mạng tensor, dùng đẳng thức tám bình phương của Degen từ thập niên 1840 để triệt tiêu các ràng buộc giao nhau. Mục Provenance trong PDF gốc Anthropic ghi thuật toán lõi tìm thấy ngày 16/10/2026 bởi một model Claude nghiên cứu nội bộ với 14 triệu output token và “no human input” cho thuật toán lõi. Các nhà nghiên cứu Anthropic sau đó làm việc cùng Claude để cải thiện cách trình bày, và bài báo ghi nhận một model nội bộ của OpenAI đã tuyên bố chứng minh một kết quả tương tự một cách độc lập và đồng thời. Hệ quả mà các bản tổng hợp thứ cấp ghi lại là bác bỏ SETH, suy ra thuật toán dưới mũ cho Independent Set, Clique, Vertex Cover, Dominating Set, và không bác bỏ giả thuyết Orthogonal Vectors.

Cách công bố khác nhau và hệ quả cho độ tin cậy

OpenAI mời chính hai người đề xuất ETH cùng Ryan Williams tổ chức nhóm rà soát công khai, trong khi Anthropic đăng thẳng lên repo, bài báo và bản Lean nằm trong thư mục ghi rõ là sản phẩm nghiên cứu, không duy trì, không nhận đóng góp, không có nhóm rà soát riêng được nêu. Điểm khác nhau này chỉ cho thấy kênh kiểm chứng sau công bố khác nhau.

Lean đã kiểm tra được gì và còn khoảng trống nào chỉ con người mới lấp được

Mình nhắc anh em một ý: Lean chạy qua rất mạnh, nhưng nó chỉ soát theo đúng đề bài được viết thành mã, nên đừng vội coi bản Lean chạy qua là chứng minh đã đúng hoàn toàn.

Bản Lean của Anthropic kiểm tra tới đâu

Thư mục eth trong repo anthropics/formal-math, giấy phép Apache 2.0, và file MainResults.lean chỉ nêu phát biểu, không chứa chứng minh, nêu hai định lý là ETHIsFalse và MainTheorem trên máy Turing của Mathlib, là mô hình máy tính của Mathlib dùng để viết ETH thành mã Lean. Lệnh kiểm tra là lake exe cache get, lake build, lake env lean scripts/PrintAxioms.lean, build khoảng 8 phút trên 24 vCPU, Lean v4.33.1 và Mathlib v4.33.1 được ghim, kết quả PrintAxioms kỳ vọng là cả hai định lý chỉ phụ thuộc 3 tiên đề chuẩn của Lean là propext, Classical.choice, Quot.sound. CI kiểm tra đầy đủ hơn bằng Comparator (công cụ đối chiếu tự động) để đối chiếu phát biểu với Challenge.lean, tức file phát biểu gốc cần đối chiếu, và kernel thứ hai viết độc lập tên nanoda, là kernel Lean thứ hai viết riêng để chạy lại chứng minh. Quy mô theo PDF gốc là 1.050 module Lean, và README thừa nhận không máy nào kiểm tra file có nói đúng như bài báo nói hay không.

Bản Lean của OpenAI yếu hơn bản thảo bao nhiêu

Mình đọc trực tiếp file 378.md thì thấy bản Lean chứng minh máy tất định đếm chính xác các cách gán thỏa mãn của k-CNF mã hoá chuẩn trên n biến trong thời gian (L+1)^O_k(1) 2^O_k(n(loglogn)^2/sqrt(logn)), trong đó L là độ dài bit của mã hoá. Cùng file nêu bản thảo ngày 25/10/2026 cho bound sắc hơn là (n+m)^O_k(1) 2^O_k(nloglogn/sqrt(logn)), nên mức yếu hơn của Lean là đúng một thừa số (log log n) trong số mũ, và khoảng chênh này không làm mất kết luận bác bỏ ETH nếu phát biểu formal khớp với ETH, vì cả hai dạng đều là 2^o(n). File comparator nêu trong 378.md là lean/ComparatorChallenges/SubexponentialSAT.lean.

Bài kiểm toán độc lập ngày 28/10 và giới hạn của nó

Bài kiểm toán độc lập ngày 28/10/2026 của Carlos Toledo, qua trang mathcommunity, chạy lại cả hai bản Lean bằng Comparator, kernel của Lean và nanoda, chứng minh phát biểu ETH dạng sách giáo khoa bị bác bỏ trong mô hình máy của mỗi lab. Giới hạn còn lại là bước nối mô hình máy với nhau và bước khớp phát biểu Lean với bài báo, nên đây là kiểm tra máy, chưa phải xác nhận của con người về toàn bộ chứng minh.

O’Donnell và Kintali là diễn giải lại, không phải kiểm chứng độc lập

Ryan O’Donnell viết bản giải thích 12 trang ngày 26/10/2026, trang mathcommunity ghi chú bản này có câu “no idea if it’s correct”, Shiva Kintali viết bản đơn giản hoá 22 trang ngày 26/10/2026, Fortnow gợi ý bắt đầu từ bài O’Donnell. Cả hai đều là diễn giải lại, chưa phải kiểm chứng độc lập, nên anh em đừng dùng hai bản này làm bằng chứng rằng chứng minh đã đúng.

Bác bỏ ETH không đồng nghĩa P bằng NP, không làm mật mã yếu đi, không làm SAT solver thực tế nhanh hơn

Đây là mục gỡ hiểu lầm dễ gặp nhất.

SETH, Gap-ETH và NSETH đi theo chiều nào

SETH là phiên bản mạnh hơn ETH, nói thời gian giải k-SAT tiến sát brute force 2^n khi k tăng dần, SETH suy ra ETH, nên bác bỏ ETH thì SETH cũng sụp theo chiều Fortnow nêu, và bài báo OpenAI còn tuyên bố bác bỏ thêm Gap-ETH và NSETH. Bài báo Anthropic nói kết quả không bác bỏ giả thuyết Orthogonal Vectors, nên nhiều cận dưới bậc hai trong P dựa vào Orthogonal Vectors vẫn có thể đứng vững.

Vì sao bound mới còn xa mới tới P bằng NP

P so với NP hỏi liệu mọi bài toán mà đáp án kiểm tra nhanh được thì có giải nhanh trong thời gian đa thức hay không, trong khi bound mới vẫn là dạng mũ nhưng số mũ thu nhỏ dần, còn xa mới tới đa thức. Fortnow nói muốn có thuật toán dưới mũ cho mọi bài toán NP thì cần giải 3-SAT trong thời gian 2^(n^o(1)), kết quả này còn xa mới tới đó, và bài báo OpenAI tự nói kết quả không suy ra thuật toán dưới mũ cho các bài toán NP nói chung, vì bound dạng 2^o(n) không truyền qua các phép rút gọn tổng quát. Greg Brockman, chủ tịch OpenAI, trên X ngày 26/10/2026 (nguồn thứ cấp, Emergent Mind và llms.blog khớp nhau), viết nguyên văn: “p still probably doesn’t equal np”. Scott Aaronson, theo các bản tổng hợp thứ cấp, nâng xác suất tự đánh giá P bằng NP từ 3% lên 5%.

Phạm vi chỉ áp cho k-SAT và hệ quả thực tế bị giới hạn

Fortnow, bài ngày 28/10/2026 đã đọc trực tiếp, nhấn mạnh thuật toán OpenAI chỉ áp cho k-SAT, không cho gì mới với Subset Sum hay Travelling Salesman. Zelinsky kết luận bound mới vẫn tệ hơn mọi bound dạng ký hiệu L cho factoring. Bài báo Anthropic tự nói kết quả không nói gì về việc giải công thức trong thực tế (theo README Anthropic).

Ngưỡng thực tế: bound mới chỉ thắng brute force ở cỡ bài toán phi thực tế

Câu hỏi thực tế là bài toán phải lớn tới đâu bound mới bắt đầu thắng brute force 2^n.

Ngưỡng đã thống nhất với điều kiện m bằng 5n

Theo Oguzhan, CellCog và câu tóm tắt phần mở đầu PDF gốc Anthropic, với công thức 3-CNF có m bằng 5n mệnh đề, bound đã chứng minh không thắng brute force 2^n trừ khi số biến vượt 10^10000.

Ngưỡng theo n đơn thuần và mâu thuẫn chưa chốt

Ngưỡng theo n đơn thuần là chỗ các bản tổng hợp thứ cấp mâu thuẫn nhau và bài này chưa chốt, vì Oguzhan nêu n lớn hơn 10^10 còn CellCog nêu n lớn hơn 10^108. Phía Oguzhan khớp câu tóm tắt phần mở đầu và câu kết Phụ lục D trong PDF gốc Anthropic, trong khi phía CellCog không tìm thấy trong toàn văn hai PDF gốc khi grep toàn văn, 108 trong PDF Anthropic chỉ là số trang trích dẫn, và nguồn gốc của con số 10^108 của CellCog vẫn chưa xác minh được, có thể là ước tính riêng của CellCog. Bài này nêu Oguzhan và paper là 10^10 kèm ghi chú CellCog nêu 10^108 nhưng chưa rõ nguồn.

Kỷ lục cũ và mốc brute force không khả thi

Theo Oguzhan và CellCog, cách tiếp cận tổng quát khó mà cải thiện được gì trừ khi n lớn hơn 10^7, trong khi brute force đã hoàn toàn không khả thi ở n bằng 100. Kỷ lục cũ, theo PDF gốc Anthropic, là thuật toán tất định 3-SAT tốt nhất trước đó O(1.328^n), thuật toán ngẫu nhiên theo dòng PPSZ O(1.308^n), đếm #3-SAT O(1.6423^n), và bound mới chỉ là tiến bộ tiệm cận.

Tới 03/11/2026, ai đang rà soát và hai phía nói gì

Tới mốc 03/11/2026, chưa có kết luận rà soát độc lập hoàn chỉnh nào được báo cáo, nhưng hai phía đã lên tiếng.

Phía hào hứng nói gì và với tư cách gì

Lance Fortnow, blog Computational Complexity ngày 28/10/2026, tự nhận chưa tự kiểm tra chứng minh, nhưng viết: “I have not verified the proof myself, but it is safe to assume now that the exponential-time hypothesis is toast.” Anh em ghi rõ đây là Ý KIẾN, chưa phải chứng nhận, và lập trường là hào hứng có điều kiện dựa trên niềm tin vào hai bản Lean độc lập. Gowers nói kết quả rất bất ngờ và có hệ quả lớn nếu đúng, Bubeck, nhà nghiên cứu OpenAI, nói đây có thể là bất ngờ lớn nhất trong 20 năm theo dõi lý thuyết độ phức tạp, Taylor nói ông vẫn sốc, và Nelson nói việc đọc chứng minh để cải thiện cách trình bày chưa đồng nghĩa kiểm chứng xong. Cộng đồng Hacker News qua llms.blog đạt 633 điểm và 271 bình luận cho thông cáo OpenAI, 427 điểm và 163 bình luận cho bài báo ETH, lập trường chung là lớn nếu đúng nhưng chưa kiểm chứng.

Phía thận trọng nói gì và với tư cách gì

Thư ngỏ ngày 26/10/2026 của Impagliazzo, Paturi, Williams trên ethdiscussion.blog, ký tên Impagliazzo, Paturi, Williams, nói: “Our involvement should not be taken as certification of the claim. A result of this significance requires careful, independent scrutiny and an understanding that others can reconstruct, question, and build upon.” Thư đề xuất họp trực tuyến cộng đồng trước cuối năm 2026. Phụ lục E của paper Anthropic nói bản Lean do AI viết, do các model cùng loại khác review, tại thời điểm viết không có người nào được biết là đã kiểm tra: “was written by AI models and reviewed by other instances of the same models; at the time of writing no person is known to have checked it”, và đây là lời của paper tại thời điểm viết. Williams nói nhóm đang làm việc để kiểm tra chứng minh, O’Donnell nói các kết quả giả định ETH không sụp đổ vì các phép rút gọn hiệu quả từ 3-SAT vẫn còn hoạt động, và Grochow nói nhiều kết quả có lẽ cứu được bằng thay đổi nhỏ.

Trạng thái kiểm chứng chốt tới 03/11/2026

Cả hai bài báo đều chưa qua peer review, nhóm rà soát OpenAI là Impagliazzo, Paturi, Williams, Fortnow cập nhật ngày 29/10 rằng nhóm đã lập trang thảo luận ethdiscussion.blog, tới ngày 01 và 02/11/2026 chưa có báo cáo kết luận rà soát hoàn chỉnh nào. Ngày 01/11/2026, theo nguồn thứ cấp Emergent Mind, Ryan Williams mở nơi công bố các kết quả mới, và ngày 02/11/2026 bản tổng hợp của Quanta, qua nguồn này, nhắc lại việc 3 nhà nghiên cứu hàng đầu sẽ kiểm tra bài báo. Ba tầng phân biệt ở đây là hãng tuyên bố, Lean kiểm tra bước chứng minh, con người còn phải kiểm tra phát biểu formal có khớp với ETH như giới lý thuyết hiểu hay không.

Nếu kết quả đúng thì điều gì thay đổi thật sự và điều gì không đổi với độc giả

Mục này trả lời: nghiên cứu cũ sẽ ra sao, và đời sống dùng máy tính hôm nay có gì khác không.

Hàng trăm bài báo dùng ETH làm nền sẽ phải xem lại ra sao

Con số hơn 800 bài báo thuộc về paper Anthropic, theo phần mở đầu PDF gốc Anthropic đã đọc trực tiếp. Đó là một lần rà soát tài liệu do Claude chạy, tìm thấy hơn 800 bài báo chứng minh ít nhất một kết quả chỉ dưới ETH hoặc một giả thuyết mạnh hơn suy ra ETH. Con số này không thuộc về OpenAI, và chưa phải con số đã được kiểm chứng độc lập, trong khi OpenAI chỉ nói hàng trăm bài báo theo blog OpenAI đã đọc trực tiếp. Fortnow, O’Donnell và Grochow đều nói các kết quả cũ chưa chắc đã sai và nhiều kết quả có lẽ cứu được bằng thay đổi nhỏ, và khối lượng rà soát lại nền móng là lớn, theo Husfeldt, nhưng không đồng nghĩa hàng trăm bài báo bỗng thành rác.

Điều không đổi trong đời sống thực tế của độc giả hôm nay

Máy tính không nhanh hơn, mật mã không yếu đi ngay, SAT solver thực tế không nhanh hơn, vì ngưỡng thắng brute force nằm ở cỡ phi thực tế, và bài báo Anthropic tự nói kết quả không nói gì về việc giải công thức trong thực tế. Bound mới vẫn tệ hơn mọi bound dạng ký hiệu L cho bài toán phân tích số nên không thắng thuật toán sàng trường số tốt nhất cho factoring theo Zelinsky. P vẫn chưa bằng NP theo Brockman và Aaronson, nên anh em không cần thay đổi lựa chọn mật mã hay công cụ chỉ vì tin này.

Độc giả nên theo dõi gì tiếp theo thay vì kết luận vội

Mình sẽ theo dõi nhóm rà soát, trang ethdiscussion.blog, cuộc họp cộng đồng trước cuối năm 2026, và nơi công bố các kết quả mới mà Ryan Williams mở ngày 01/11/2026 theo nguồn thứ cấp Emergent Mind. Tiêu chí cập nhật sau này là có báo cáo rà soát độc lập hoàn chỉnh nào không, phát biểu formal có được xác nhận khớp với ETH hay không, và ngưỡng theo n đơn thuần có được chốt hay vẫn giữ mâu thuẫn 10^10 và 10^108. Mình mời anh em là dân nghiên cứu hoặc dân làm solver chia sẻ góc nhìn thực tế.

Kết luận: hai tuyên bố lớn, một bản kiểm tra bằng máy, và một cuộc rà soát vẫn đang chạy

Tới 03/11/2026, câu chuyện gọn lại thành hai lab cùng tuyên bố bác bỏ giả thuyết ETH bằng thuật toán dưới mũ, Lean đã chạy qua, con người vẫn đang kiểm tra phát biểu formal. OpenAI tuyên bố bound bản thảo và bản Lean yếu hơn đúng một thừa số (log log n) trong số mũ, Anthropic tuyên bố bound 2^O(min{knloglogn/sqrt(logn),km/sqrt(logm)}) với 14 triệu output token và 1.050 module Lean, con người còn phải kiểm tra phát biểu formal có khớp với ETH hay không. Thư ngỏ nhóm rà soát nói “should not be taken as certification of the claim”, và câu Fortnow là ý kiến kèm tự nhận chưa tự kiểm tra. Hàng trăm bài báo, với nhãn hơn 800 thuộc paper Anthropic, sẽ phải xem lại nền móng nhưng chưa chắc đã sai, trong khi máy tính, mật mã và SAT solver hôm nay không đổi, và P vẫn chưa bằng NP. Anh em theo dõi tiếp nhóm rà soát, trang ethdiscussion.blog và cuộc họp cộng đồng trước cuối năm 2026.

Nguồn tham khảo

• Blog OpenAI: https://openai.com/index/building-scientific-understanding-with-academic-communities/
• Bài báo OpenAI, PDF gốc: https://raw.githubusercontent.com/openai/math/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf
• File Lean OpenAI 378: https://raw.githubusercontent.com/openai/math/main/lean/docs/378.md
• Repo Anthropic, thư mục eth: https://github.com/anthropics/formal-math/tree/16a5ce41304fcdaea4e0be7c132e1c361dc26da5/eth
• Bài báo Anthropic, PDF gốc: https://raw.githubusercontent.com/anthropics/formal-math/main/eth/paper.pdf
• Bài báo Anthropic trên Hexagon: https://hexagonmath.org/2610.00577v1
• Thư ngỏ nhóm rà soát: https://ethdiscussion.blog/2026/10/26/eth-refutation-examination-and-discussion/
• Blog Fortnow: https://blog.computationalcomplexity.org/2026/10/the-exponential-time-refutation.html
• Trang soi chiếu repo OpenAI: https://mathcommunity.github.io/oai-math-revised/papers/The-Exponential-Time-Hypothesis-is-False-October-25-2026/
• Emergent Mind: https://www.emergentmind.com/exponential-time-hypothesis
• Oguzhan: https://www.oguzhan.co/exponential-time-hypothesis-false-openai-anthropic-3-sat/
• CellCog: https://cellcog.ai/blog/claude-refutes-eth-3-sat/
• llms.blog: https://www.llms.blog/posts/what-people-are-saying-about-openais-claim-that-its-ai-disproved-the-exponential-time-hypothesis