asd

Các phương pháp tiếp cận các bài toán NP-đầy đủ có giúp tính gần đúng các bài toán NP khác không?

Nếu ký ức của tôi về Khoa học Máy tính Lý thuyết vẫn còn đúng, thì các giải pháp cho các bài toán NP-hoàn chỉnh có thể được sử dụng để giải các bài toán NP khác, bằng cách chuyển đổi một vấn đề này thành một vấn đề khác. Rõ ràng có những phép gần đúng khá tốt cho một số bài toán NP-đầy đủ. Rõ ràng MAX-CUT có thể được tìm thấy tới 87% giải pháp lý tưởng. Sau đó, bạn có thể sử dụng điều này để nói rằng chúng ta có thể chuyển đổi các bài toán NP khác thành MAX-CUT, và do đó cũng đạt được giải pháp chính xác lên đến x% không? Tôi sẽ không nghĩ như vậy, bởi vì ai đó đã nói điều đó rồi. Nhưng có lý do tại sao không?

Nó đang đọc từ [ http://people.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf ] rằng tôi đã đến câu hỏi này.

Người hỏi: Tháng 1, 24 năm

Câu trả lời

Mọi bài toán NP-đầy đủ đều có đặc tính là nếu bạn có một phương pháp giải hiệu quả cho nó, thì bạn sẽ có một phương pháp giải hiệu quả cho tất cả các bài toán trong NP.

Sau đó, chúng ta đang nói một cách cổ điển về các vấn đề quyết định, hoặc các vấn đề với một đầu ra chính xác, rời rạc.
Như bạn nhận thấy, cũng có những vấn đề về tối ưu hóa mà chúng tôi muốn tối ưu hóa một số lượng nhất định. Các bài toán như vậy cũng thường (không phải lúc nào cũng) NP-đầy đủ, và đối với một số bài toán NP-đầy đủ, có các phương pháp xấp xỉ hiệu quả với đảm bảo chất lượng của phép gần đúng. Tuy nhiên, như bạn đã nghi ngờ, điều này bây giờ KHÔNG có nghĩa là bạn có một phương pháp gần đúng hiệu quả cho TẤT CẢ các bài toán tối ưu hóa trong NP.
Thật vậy, như Fortnow đã chỉ ra trong bài viết của mình, có một số vấn đề về tối ưu hóa NP nhất định khó tiếp cận một cách hiệu quả (với sự đảm bảo về chất lượng) khi giải quyết chúng chính xác ngay lập tức. Do đó, tiếp cận luôn là một lựa chọn.
Vì vậy, đối với lời giải chính xác, các bài toán NP-đầy đủ đều khó như nhau, nhưng đối với tính gần đúng, một số có vẻ khó hơn các bài toán khác. Sao bạn hỏi vậy? Chúng tôi không thực sự biết. Các kỹ thuật rút gọn giữa các bài toán không phải lúc nào cũng có thể mở rộng đến các phép gần đúng (đôi khi chúng được, Papadimitriou và Yannakakis xuất bản một bài báo quan trọng về vấn đề này vào năm 1991). Nhân tiện, tất nhiên vẫn có thể là NP bằng P và mọi thứ trong NP hóa ra có thể giải được chính xác một cách hiệu quả. Bí ẩn lớn vẫn còn.

Trả lời bởi

Jan Van den Bussche

khoa học máy tính tin sinh học sinh thái học

Đại học Hasselt
Tòa nhà cơ sở của Đại học Agoralaan D BE-3590 Diepenbeek
http://www.uhasselt.be/

Recent Articles

spot_img

Related Stories

Stay on op - Ge the daily news in your inbox