The P versus NP problem [(Tập vấn đề) P so với (tập vấn đề) NP] vốn là 1 trong 7 “thách thức thiên niên kỷ” được Viện Toán Clay của Mỹ sẵn sàng trao giải thưởng 1 triệu USD cho người giải được.
 |
| P không tương đương NP... |
Nghiên cứu viên chính của Bộ phận Nghiên cứu ở HP Vinay Deolalikar vừa công bố lời giải bài toán về đẳng thức của các lớp phức tạp P và NP (The P versus NP problem - Tập vấn đề P so với tập vấn đề NP) vốn là 1 trong 7 “thách thức thiên niên kỷ” được Viện Toán Clay của Mỹ sẵn sàng trao giải thưởng 1 triệu USD.
Cho đến nay, mới chỉ có 1 trong số 7 bài toán đó đã được thừa nhận là được giải xong: Bài toán chứng minh giả thuyết của Poincaré do nhà toán học Nga Grigori Perelman thực hiện.
Bài toán về đẳng thức của các lớp phức tạp P và NP nằm ở nỗ lực giải thích xem liệu có lý hay không dự đoán về việc, nếu vấn đề nào đó có thể dễ dàng kiểm tra bằng phương pháp chọn lọc ngẫu nhiên thì cả câu trả lời cho vấn đề đó cũng có thể chọn lọc đủ nhanh. Đẳng thức có ý nghĩa ở chỗ nó cho phép giải nhanh hơn nhiều bài toán phức tạp so với hiện tại.
Deolalikar đã chứng minh sự phức tạp của P và NP là không đồng đều (P ≠ NP) và cái gọi là những bài toán NP đầy đủ có thể giải chỉ trong một thời gian nhanh hơn gấp bội là có tồn tại.
Viện Toán Clay tạm thời chưa khẳng định chứng minh của Deolalikar còn các nhà toán học nghiên cứu vấn đề này thì cho biết đã tìm thấy trong lời giải của Deolalikar của HP hàng loạt điểm “tính toán chưa tới”. Deolalikar đang làm việc với phiên bản chứng minh mới có những bổ sung cần thiết.