Mối quan hệ giữa các vấn đề NP-hard và undecidable

Question

Có một chút nhầm lẫn về mối quan hệ giữa các vấn đề không thể giải quyết và các vấn đề về NP khó. Cho dù NP khó khăn vấn đề là một tập hợp con của các vấn đề undecidable, hoặc là họ chỉ giống nhau và bằng nhau, hoặc là nó mà họ không thể so sánh?

Đối với tôi, tôi đã tranh luận với bạn bè rằng các vấn đề không thể giải quyết là sự thay thế cho các vấn đề khó khăn của NP. Sẽ tồn tại một số vấn đề không có trong NP cứng nhưng không thể giải quyết được. Nhưng tôi thấy lập luận này yếu đuối và bối rối một chút. Có vấn đề NP-hoàn thành mà không thể xác định.? là có bất kỳ vấn đề trong NP cứng đó là decidable. ??

Một số cuộc thảo luận sẽ hữu ích! Cảm ơn!

Answer 1

Undecidable = unsolvable cho một số yếu tố đầu vào. Không có vấn đề bao nhiêu (hữu hạn) thời gian bạn cung cấp cho thuật toán của bạn, nó sẽ luôn luôn là sai trên một số đầu vào.

NP-hard ~ = thời gian chạy siêu đa thức (giả sử P! = NP). Đó là tay lượn sóng, nhưng về cơ bản NP-cứng có nghĩa là nó là ít nhất khó như các vấn đề khó khăn nhất trong NP.

Có những vấn đề chắc chắn là NP-hard không thể giải quyết được (= có thể giải mã). Bất kỳ vấn đề NP-hoàn thành sẽ là một trong số họ, nói SAT.

Có vấn đề không thể xác định nào không phải là NP-cứng không? Tôi không nghĩ như vậy, nhưng nó không phải là dễ dàng để loại trừ nó ra - Tôi không thấy một lập luận rõ ràng rằng phải có một giảm từ SAT cho tất cả các vấn đề có thể undecidable. Có thể có một số vấn đề không thể giải thích lạ mà không phải là rất hữu ích. Nhưng các vấn đề tiêu chuẩn không thể giải quyết (vấn đề dừng lại, nói) là NP-cứng.

Answer 2

NP-hard là vấn đề là ít nhất khó như bất kỳ vấn đề NP-complete nào.

Do đó, một vấn đề không thể giải quyết có thể là NP-hard. Một vấn đề là NP-hard nếu một oracle cho nó sẽ làm cho việc giải quyết các vấn đề NP-complete dễ dàng (tức là có thể giải được trong thời gian đa thức). Chúng ta có thể tưởng tượng một vấn đề không thể giải quyết được như vậy, cho một oracle cho nó, NP-hoàn thành vấn đề sẽ được dễ dàng để giải quyết. Ví dụ, rõ ràng mỗi oracle mà giải quyết vấn đề ngăn chặn cũng có thể giải quyết một vấn đề NP-đầy đủ, vì vậy mọi vấn đề Turing hoàn tất cũng là NP-hard theo nghĩa là một (nhanh) oracle cho nó sẽ làm cho việc giải quyết các NP-đầy đủ vấn đề một cách dễ dàng.

Do đó các vấn đề không thể giải quyết được Turing-complete là tập con của các vấn đề NP-hard.

Answer 3

Sự cố không thể giải quyết, ví dụ: Turing Halting Problem chỉ là NP-Hard.

    <---------NP Hard------> 
|------------|-------------||-------------|------------|--------> Computational Difficulty 

|<----P--->| 

|<----------NP---------->| 

|<-----------Exponential----------->| 

|<---------------R (Finite Time)---------------->| 

Trong biểu đồ này, ống nhỏ hiển thị chồng chéo NP và NP-Hard và hiển thị NP-Đầy đủ, tức là tập hợp các vấn đề đó là NP cũng như NP-Hard.

vấn đề undecidable là những vấn đề NP cứng mà không có giải pháp và không trong NP.