eN-Pê

Hàn Thuỷ đã dũng cảm muốn phổ biến một số vấn đề (récursivité, complexité...) rất mũi nhọn trong tin học cơ bản. Trong điều kiện ấy, cách trình bày có thể đưa đến bàn luận, đó là lẽ thường. Tuy nhiên, điều đáng tiếc là gieo rắc những nhầm lẫn. Đặc biệt là một vỏ sò (coquille) trong định nghĩa (giải thuật) loại NP (đoạn hai, bài H.T., Diễn Đàn số 20). Không, NP không có nghĩa là non polynomial mà là non deterministe polynomial, (không tất định đa thức), ý nghĩa khác hẳn.

Nói không qua hình thức thì:

– Một giải thuật “tất định” (déterministe) phải làm đủ mọi con toán, trong khi một giải thuật “không tất định” (non déterministe) có khả năng chọn lựa ngay “đúng” quyết định, nếu quyết định ấy có thể có.

– Một bài toán nhị nguyên (chỉ cần trả lời có / không) được gọi là thuộc loại NP nếu nó chấp nhận một giải thuật không tất định phức tạp vào loại đa thức để tiến tới trả lời “có”, còn khi trả lời “không” thì không rút ra được kết luận gì!

– Định nghĩa mà H.T. dùng là để cho những giải thuật tất định được gọi là thuộc loại “biến thiên mũ” (exponentiel). Một giải thuật NP có thể được quy về một giải thuật tất định biến thiên mũ, nhưng ngược lại không đúng.

N. H. XƯƠNG ,

Trường đại học Grenoble

Vọng ngôn về những vấn đề mình chỉ biết lõm bõm thì phải chịu cái rủi ro là “múa rìu qua mắt thợ ", được những chuyên gia để mắt phê bình là đáng mừng, cảm ơn anh về những chỉ dẫn hoàn toàn chính xác ở trên. Biến NP non déterministe polynomial thành NP non polynomial là sai to về mặt thuật ngữ, xin tạ lỗi độc giả. Lý do là đã sao chép theo một nhà thiên văn và tác giả phổ biến khoa học có tiếng (J. D. Barrow, The World within the World, tr. 266). Một tác giả khác đã được tham khảo (R. Penrose, The Emperor’s New Mind, tr. 140-145, hai sách này đã dẫn một lần trước) nói rằng loại NP không thuộc loại P, và không chú thích NP, trong trường hợp đó rất dễ hiểu lầm về mặt câu chữ. Có lẽ hai tác giả này đành chịu nhập nhằng vì muốn tránh nói đến khái niệm giải thuật không tất định. Về nội dung, theo thiển ý, trong khung cảnh bình thường, những giải thuật được hiểu là tất định (giải thuật không tất định là cái rất ít người biết) thì ý nghĩa (déterministe) non polynomial này của NP không sai lắm và đủ để hiểu đại ý vấn đề phức tạp trong giải thuật. Có lẽ tệ hơn cả là trong bài viết cho rằng nếu giải quyết được hành trình của người chào hàng bằng một giải thuật (déterministe) P thì có thể giải quyết trên thực tế mọi bài toán, lại vọng ngôn nữa! chính xác ra phải nói: ...phần lớn những bài toán gặp trong thực tế.

Đến đây xin phát triển thêm một chút những định nghĩa anh đưa ra: có thể hiểu một giải thuật không tất định như những giải thuật thông thường cộng thêm một điều mới: động tác quyết định một giải pháp rất nhanh khi phải lựa chọn, mà không xét tới tất cả các giải pháp. Nhưng nếu đòi hỏi chỉ có một trả lời duy nhất đúng (chẳng hạn một giải pháp tối ưu tuyệt đối) thì kèm theo động tác trên phải kiểm soát lại để bảo đảm yêu cầu đó. Vì sự kiểm soát thường dễ hơn sự tìm ra giải pháp, nên hoạt động của giải thuật có thể phức tạp đa thức, giá phải trả là có thể phát hiện đã quyết định sai (có lẽ thường là sai, cách giải quyết bài toán thời gian tất định bằng một phương pháp không tất định này chỉ hữu ích trên mặt lý thuyết). Khi đó thì giải thuật đành phải bỏ cuộc (nói bỏ cuộc rõ hơn nói “không”, vì khi nói bỏ cuộc không biết là có hay không có giải pháp, chỉ có thể nói là giải thuật không tìm ra). Một kết quả rất quan trọng là người ta đã thấy trên một số vấn đề (tuy không tất cả), nếu đòi hỏi một giải pháp duy nhất đúng thì chỉ tìm được những giải thuật hoặc NP hoặc tất định biến thiên mũ, còn nếu bằng lòng với một trong những đáp số gần đúng thì có thể giải quyết vấn đề với độ phức tạp đa thức (kể cả thời gian làm những chọn lựa không tất định) mà không bỏ cuộc. Đó cũng là điều mà bài viết muốn nói, theo ngôn ngữ phổ thông.

H.T.