Một chứng minh đơn giản rằng ETH là sai — và vì sao giới lý thuyết tính toán đang xôn xao

Một bài báo mới xuất hiện trên Hacker News với tiêu đề đầy thách thức: "A simplified proof of ETH is False" (tạm dịch: "Một chứng minh đơn giản rằng ETH là sai"). Với những người làm trong lĩnh vực khoa học máy tính lý thuyết, đây là tuyên bố không hề nhỏ — bởi ETH (Exponential Time Hypothesis — Giả thuyết thời gian hàm mũ) là một trong những trụ cột của lý thuyết độ phức tạp tính toán hiện đại.

Bài viết hiện chỉ là một tệp PDF đăng trên trang cá nhân của tác giả, chưa qua bình duyệt (peer review), và mới chỉ thu hút được 4 điểm cùng 0 bình luận trên Hacker News. Tuy vậy, nội dung bên trong đủ để khiến cộng đồng nghiên cứu phải chú ý.

ETH là gì và vì sao nó quan trọng?

Giả thuyết thời gian hàm mũ (ETH) được đề xuất bởi Impagliazzo và Paturi vào năm 1999. Nội dung cốt lõi của nó khá kỹ thuật nhưng có thể tóm gọn như sau:

Không tồn tại thuật toán nào giải bài toán 3-SAT trong thời gian dưới hàm mũ, tức là nhanh hơn đáng kể so với việc thử mọi khả năng.

Nghe có vẻ trừu tượng, nhưng ETH là nền móng cho rất nhiều kết quả trong khoa học máy tính lý thuyết:

• Nó được dùng để chứng minh giới hạn dưới cho hàng loạt bài toán tối ưu, bài toán đồ thị, bài toán chuỗi.
• Nó là cơ sở để lập luận rằng nhiều bài toán không thể có thuật toán "gần đúng nhanh" trừ khi P = NP.
• Nó ảnh hưởng đến cả những lĩnh vực ứng dụng như mật mã học, tối ưu hóa tổ hợp, và thiết kế thuật toán trong thực tế.

Nếu ETH bị bác bỏ, nhiều kết quả "không thể làm tốt hơn" trong khoa học máy tính sẽ mất đi chỗ dựa lý thuyết. Nói cách khác, giới hạn mà chúng ta tưởng là tuyệt đối có thể chỉ là giới hạn của hiểu biết hiện tại.

Điều gì khiến tuyên bố này đáng chú ý?

Việc bác bỏ ETH không phải là chuyện mới. Đã có nhiều nỗ lực trước đây, nhưng hầu hết đều vấp phải các lỗ hổng kỹ thuật hoặc bị cộng đồng phát hiện sai sót. Điểm khiến bài báo này thu hút sự chú ý nằm ở chữ "simplified" (đơn giản hóa):

• Tác giả tuyên bố có một chứng minh ngắn gọn, dễ kiểm chứng hơn các nỗ lực trước.
• Một chứng minh đơn giản có nghĩa là cộng đồng có thể kiểm tra nhanh hơn và phát hiện lỗi (nếu có) một cách rõ ràng.
• Trong toán học và khoa học máy tính lý thuyết, sự đơn giản đôi khi là dấu hiệu của một bước đột phá thực sự — nhưng cũng thường là dấu hiệu của một sai lầm tinh vi bị che giấu.

Cần đọc với sự thận trọng

Ở thời điểm hiện tại, cần nhấn mạnh rằng đây chưa phải là một kết quả được công nhận. Có vài lý do để giữ thái độ hoài nghi lành mạnh:

• Chưa qua bình duyệt: Bài báo chỉ là một PDF tự đăng, không có xác nhận từ tạp chí hay hội nghị chuyên ngành.
• Lịch sử cho thấy tỉ lệ thành công thấp: Rất nhiều tuyên bố "chứng minh P ≠ NP" hay "bác bỏ ETH" trước đây đều thất bại khi bị kiểm tra kỹ.
• Cộng đồng chưa phản hồi: Với 0 bình luận trên Hacker News, chưa có ai đưa ra đánh giá kỹ thuật đáng tin cậy.

Với độc giả Việt Nam quan tâm đến khoa học máy tính lý thuyết — đặc biệt là sinh viên và nghiên cứu sinh ngành CNTT — đây là cơ hội tốt để theo dõi cách cộng đồng học thuật phản ứng. Những tranh luận kiểu này thường là bài học quý về cách khoa học tự kiểm chứng: một tuyên bố táo bạo chỉ có giá trị sau khi vượt qua được sự soi xét của nhiều người độc lập.

Kết luận

Bài báo "A simplified proof of ETH is False" là một tuyên bố gây chú ý nhưng chưa được kiểm chứng. Nếu đúng, nó sẽ là một trong những kết quả lớn nhất của khoa học máy tính lý thuyết trong nhiều thập kỷ. Nếu sai, nó sẽ nhanh chóng bị cộng đồng chỉ ra lỗ hổng — và đó cũng là một phần bình thường của tiến trình khoa học.

Bạn có thể đọc trực tiếp bản PDF tại địa chỉ gốc của tác giả và theo dõi thảo luận trên Hacker News để cập nhật phản hồi từ cộng đồng kỹ thuật quốc tế.