Bài toán P và NP hỏi: nếu một lời giải có thể được kiểm tra nhanh, thì liệu nó có luôn được tìm ra nhanh không. Kiểm tra một bức xếp hình đã ghép đúng chỉ mất một cái liếc, còn tự ghép thì lâu hơn nhiều. Câu hỏi là khoảng cách ấy có phải là bản chất, hay chỉ vì ta chưa tìm ra cách thông minh hơn.
Chào bạn, đây là Nhà Học Thuật. Đây có lẽ là câu hỏi mở quan trọng nhất của khoa học máy tính, có treo giải một triệu đô la Mỹ, và nếu được trả lời theo hướng bất ngờ, thế giới số mà ta biết sẽ đổi khác. Tập này mình giải thích nó không cần ký hiệu nào.
Giải nhanh và kiểm tra nhanh
Trong khoa học máy tính, nhanh có nghĩa chính xác: thời gian giải tăng lên vừa phải khi bài toán lớn dần, không bùng nổ. Lớp P gồm những bài toán giải được nhanh theo nghĩa ấy, như sắp xếp một danh sách, tìm đường ngắn nhất trên bản đồ.
Lớp NP gồm những bài toán mà nếu ai đó đưa cho bạn một lời giải, bạn kiểm tra được nhanh nó có đúng không. Ô số sudoku cỡ lớn là ví dụ: điền xong thì kiểm tra rất dễ, nhưng tự điền thì có thể rất khó.
Mọi bài toán trong P đều thuộc NP, vì đã giải nhanh được thì kiểm tra càng nhanh. Câu hỏi là chiều ngược lại: mọi bài toán trong NP có thuộc P không. Nói cách khác, kiểm tra dễ có kéo theo giải dễ không.
Đa số các nhà khoa học máy tính tin rằng P khác NP, tức có những bài toán kiểm tra dễ mà giải khó về bản chất. Nhưng niềm tin chưa phải chứng minh.
Bài toán NP đầy đủ: những vị vua của độ khó
Năm một nghìn chín trăm bảy mươi mốt, Stephen Cook chứng minh rằng có một bài toán trong NP đặc biệt: nếu giải nhanh được nó, thì giải nhanh được mọi bài toán trong NP. Leonid Levin ở Liên Xô độc lập tìm ra kết quả tương tự. Những bài toán như vậy gọi là NP đầy đủ.
Năm sau, Richard Karp chỉ ra hơn hai chục bài toán quen thuộc cũng NP đầy đủ. Từ đó tới nay, hàng nghìn bài toán thực tế được xếp vào lớp này: xếp lịch, chia hàng lên xe, thiết kế mạch, gấp protein trong một số mô hình, và nhiều trò chơi đố.
Ví dụ dễ hình dung là bài toán người bán hàng: có danh sách thành phố, hỏi có lộ trình đi qua tất cả mà tổng quãng đường dưới một mức cho trước không. Kiểm tra một lộ trình thì dễ. Tìm ra nó, với hàng trăm thành phố, có thể vượt quá sức mọi máy tính.
Điều kỳ diệu là các bài toán NP đầy đủ trông rất khác nhau, nhưng về độ khó, chúng là một. Giải nhanh được một bài là giải nhanh được tất cả.
Gödel đã đoán trước câu hỏi
Năm một nghìn chín trăm năm mươi sáu, Kurt Gödel viết một lá thư cho John von Neumann khi ấy đang lâm bệnh nặng. Trong thư, Gödel hỏi về độ khó của việc tìm chứng minh cho một mệnh đề toán học có độ dài cho trước, về thực chất là một dạng của câu hỏi P và NP.
Gödel nhận xét rằng nếu việc ấy làm được nhanh, thì phần lớn công việc sáng tạo của nhà toán học có thể giao cho máy. Lá thư chỉ được biết rộng rãi nhiều năm sau, khi lĩnh vực đã tự tìm ra câu hỏi.
Nhận xét của Gödel chỉ ra lý do câu hỏi quan trọng vượt khỏi tin học. Kiểm tra một chứng minh, một bản nhạc hay, một thiết kế đẹp thường dễ hơn nhiều so với nghĩ ra nó. Nếu P bằng NP, khoảng cách ấy theo một nghĩa nào đó sẽ biến mất.
Nhiều nhà nghiên cứu xem đây là trực giác mạnh nhất cho việc P khác NP: thế giới mà sáng tạo dễ như thưởng thức có vẻ không giống thế giới ta đang sống.
Nếu P bằng NP thì sao?
Phần lớn mật mã hiện đại dựa vào những bài toán được tin là khó giải mà dễ kiểm tra. Nếu P bằng NP và có thuật toán thực sự nhanh, nhiều hệ thống mã hoá sẽ sụp đổ. Cần lưu ý một số bài toán dùng trong mật mã, như phân tích số lớn ra thừa số nguyên tố, chưa được chứng minh là NP đầy đủ.
Mặt khác, tối ưu hoá sẽ có bước nhảy vọt: lịch trình, hậu cần, thiết kế thuốc, nhiều bài toán đang phải dùng lời giải gần đúng sẽ có lời giải tốt nhất.
Nhưng cũng có khả năng P bằng NP mà thuật toán chậm đến mức vô dụng trong thực tế, hoặc chứng minh chỉ cho biết thuật toán tồn tại mà không chỉ cách tìm. Toán học có cách gây bất ngờ như vậy.
Và ngay cả khi P khác NP như đa số tin, ngoài đời nhiều bài toán NP đầy đủ vẫn được giải tốt trong những trường hợp cụ thể, nhờ các phương pháp khôn ngoan. Độ khó trường hợp xấu nhất không phải lúc nào cũng là độ khó ta gặp.
Vì sao chứng minh khó đến vậy?
Muốn chứng minh P khác NP, phải chỉ ra rằng không có thuật toán nhanh nào, kể cả những thuật toán chưa ai nghĩ ra, giải được một bài NP đầy đủ. Chứng minh điều không tồn tại về mọi phương pháp có thể có là việc cực khó.
Các nhà nghiên cứu đã chứng minh được rằng một số kỹ thuật chứng minh quen thuộc không thể đủ sức giải quyết câu hỏi này. Đó là những định lý về rào cản: chúng cho biết hướng nào chắc chắn sẽ thất bại.
Thỉnh thoảng lại có người công bố chứng minh, đôi khi được truyền thông đưa tin rầm rộ. Cho tới nay, chưa chứng minh nào vượt qua được sự thẩm định của giới chuyên môn.
Có nhà khoa học nói vui rằng câu hỏi này có thể chờ thêm một thế kỷ. Trong lúc chờ, lần tới bạn giải xong một ô sudoku khó, hãy nhớ rằng mình vừa chạm vào một câu hỏi trị giá một triệu đô la Mỹ.
Câu hỏi thường gặp
P và NP là viết tắt của gì?
P là thời gian đa thức, nghĩa là thời gian giải tăng vừa phải theo kích thước bài toán. NP là thời gian đa thức không tất định, một cách nói kỹ thuật cho việc lời giải có thể được kiểm tra trong thời gian đa thức.
Máy tính lượng tử có giải được bài toán NP đầy đủ nhanh không?
Theo hiểu biết hiện nay, không có bằng chứng máy tính lượng tử giải nhanh được các bài toán NP đầy đủ nói chung. Chúng mạnh với một số bài toán đặc biệt như phân tích thừa số, nhưng đó là chuyện khác.
Có bao nhiêu nhà khoa học tin P khác NP?
Các cuộc thăm dò không chính thức trong giới chuyên môn cho thấy đa số áp đảo tin rằng P khác NP. Tuy vậy, đây vẫn là niềm tin dựa trên kinh nghiệm, không phải chứng minh.
Sudoku có thật sự là bài toán NP đầy đủ không?
Sudoku ô chín nhân chín thì máy giải rất nhanh. Phiên bản tổng quát với lưới kích thước tuỳ ý mới được chứng minh là NP đầy đủ.
Giải bài toán P và NP được thưởng bao nhiêu?
Viện Toán học Clay treo giải một triệu đô la Mỹ cho lời giải được công nhận, dù câu trả lời là P bằng NP hay P khác NP.
