KHI SỐ 1 ĐẮT HƠN SỐ 0, NÉN DỮ LIỆU TRỞ NÊN KHÓ

Để lưu trữ hay gửi đi một văn bản một cách gọn nhẹ, hãy gán cho mỗi ký hiệu một từ gồm các số 0 và 1, ngắn cho những ký hiệu thường gặp và dài hơn cho những ký hiệu hiếm. Các từ phải tạo thành một mã tiền tố (prefix code): không từ nào được là phần đầu của một từ khác. {0, 10, 11} hợp lệ; {0, 01, 11} thì không, vì 0 là phần mở đầu của 01. Với một mã tiền tố, một chuỗi bit dài có thể được cắt trở lại thành các từ mà không cần bất kỳ dấu phân cách nào.

Mã tốt nhất thuộc loại này — mã có độ dài trung bình nhỏ nhất — được tìm ra vào năm 1952 bởi D. A. Huffman, với một công thức tham lam (greedy) đơn giản và chạy nhanh.

Khi các chữ cái có giá

Công thức của Huffman giả định rằng một chữ 0 và một chữ 1 có chi phí như nhau. Giả sử không phải vậy: chữ 1 mất nhiều thời gian hơn để truyền đi, hoặc chiếm nhiều chỗ hơn để lưu trữ. Khi đó mỗi từ có chi phí bằng tổng chi phí các chữ cái của nó, và thành phần của một từ cũng quan trọng như độ dài của nó. Chẳng hạn, với chi phí 1 và 3, 00 và 01 dài bằng nhau nhưng có chi phí lần lượt là 2 và 4.

Biến thể này có một lịch sử lâu dài. R. M. Karp đã viết nó dưới dạng một bài toán quy hoạch nguyên (integer programming) vào năm 1961. Các công trình sau đó đã tìm ra những thuật toán chính xác và hiệu quả cho mọi cặp cố định chi phí nguyên, cùng một lược đồ xấp xỉ có thể tiến gần tối ưu tùy ý. Nhưng khi bản thân các chi phí là một phần của dữ liệu đầu vào, không ai biết bài toán khó đến mức nào. Mãi đến năm 2021, nó vẫn còn được liệt kê là một bài toán mở.

Câu trả lời: NP-đầy đủ

L. Sunil Chandran, thuộc Viện Khoa học Ấn Độ (Indian Institute of Science) ở Bengaluru, và Rishikesh Gajjala, thuộc Pramaana Labs, nay chứng minh rằng việc quyết định xem có tồn tại một mã có chi phí tối đa là K hay không là NP-đầy đủ — ngay cả khi hai chi phí là hai số nguyên liên tiếp, M và M + 1. Các nhà khoa học máy tính gọi một bài toán là NP-đầy đủ khi nó khó ngang với cả một họ các bài toán kinh điển: một phương pháp tổng quát nhanh cho một bài toán sẽ cho ra một phương pháp nhanh cho tất cả, và chưa ai biết phương pháp nào như vậy. Do đó, việc tìm ra mã rẻ nhất là NP-khó (NP-hard).

Điều này không mâu thuẫn với các thuật toán nhanh cho chi phí cố định. Trong chứng minh, M tăng theo dữ liệu đầu vào; với mọi cặp chi phí được cố định từ trước, những thuật toán đó vẫn áp dụng được.

Một câu đố ẩn trong cây mã

Chứng minh bắt đầu từ một bài toán khó đã biết: trong một mạng lưới được vẽ trên một tờ giấy mà không có đường nào cắt nhau, liệu có thể chọn k điểm sao cho không có hai điểm nào được nối với nhau? Sau đó nó xây dựng một bài toán mã hóa mà mã rẻ nhất của nó trả lời câu hỏi đó.

1. Mọi mã tiền tố đều là một cây: 0 đi sang trái, 1 đi sang phải. Một từ ở độ sâu d có z chữ 1 có chi phí M × d + z khi các chữ cái có chi phí M và M + 1. Độ sâu quyết định phần lớn của chi phí, còn số chữ 1 quyết định phần nhỏ.
2. Các tác giả thiết kế một bài toán trung gian mới: cố định số lá của cây ở mỗi độ sâu, và chấm điểm vị trí các lá của nó. Họ chỉ ra rằng một cây rẻ, khi lớn dần từng tầng một, buộc phải chạy một chương trình nhỏ kiểm tra lần lượt từng điểm được chọn, sao chép từng lựa chọn và kiểm tra mọi liên kết. Mọi đường tắt đều tốn thêm ít nhất một đơn vị; mỗi điểm được chọn tiết kiệm đúng một đơn vị.
3. Cuối cùng, các tần suất được tinh chỉnh sao cho mỗi ký hiệu bị buộc phải nằm ở đúng độ sâu, và điểm số trở thành chi phí mã hóa cộng với một lượng cố định.

Một ví dụ nhỏ trong bài báo cho thấy các chi phí tinh tế đến mức nào. Ba ký hiệu có tần suất 20, 12 và 9, và các chữ cái có chi phí 83 và 84. Mã (0, 10, 11) có chi phí 5.176. Mã (1, 00, 01) có chi phí 5.175: trao chữ cái đắt tiền cho ký hiệu thường gặp nhất lại có lợi hơn, vì khi đó hai từ còn lại mang ít chữ 1 hơn.

Nơi ẩn giấu cái khó

Một kết quả thứ hai xác định chỗ khó khăn nằm ngay bên trong việc mã hóa thông thường. Công thức của Huffman tìm ra độ dài trung bình ngắn nhất một cách nhanh chóng. Nhưng trong số tất cả các mã đạt được độ dài đó, việc chọn ra mã có ít chữ 1 nhất, tính theo trọng số tần suất, cũng là NP-đầy đủ.

Vẫn còn những câu hỏi: liệu bài toán có còn khó khi mọi con số đều nhỏ hay không (cái gọi là NP-khó mạnh, strong NP-hardness), và liệu một lược đồ nhanh có thể xấp xỉ tối ưu với độ chính xác tùy ý, với thời gian chạy cũng chỉ tăng ở mức hợp lý theo độ chính xác đó hay không.

Một chứng minh được tìm ra cùng AI

Bài báo nói rõ chứng minh đã được tìm ra như thế nào. Trước tiên, các tác giả nhờ Codex của OpenAI đưa ra một chứng minh về độ khó cho một bài toán tổng quát hơn, rồi yêu cầu nó mở rộng chứng minh sang các mã không nhị phân và cuối cùng sang mã nhị phân. Codex đã đóng góp vào chiến lược của phép quy dẫn và sự phát triển toán học của nó; nó cũng giúp soạn thảo, kiểm tra các lập luận và xây dựng các ví dụ. Các tác giả định hướng công việc, yêu cầu sửa chữa và đơn giản hóa, viết lại phần trình bày một cách đáng kể, và chịu trách nhiệm về các phát biểu và chứng minh cuối cùng. Như mọi bản tiền ấn phẩm (preprint), nó chưa được bình duyệt.