(Tôi xin lỗi nếu đây là trang web sai cho câu hỏi này, nhưng cho rằng có nhiều câu hỏi lý thuyết "không-đủ-cho-CS-lý thuyết" trôi nổi ở đây, tôi nghĩ rằng điều này có thể phù hợp . Xin vui lòng để di chuyển này nếu nó không phù hợp.)Chứng minh rằng sự cố tạm dừng là NP-hard?
trong this answer cho một câu hỏi về các định nghĩa của NP, NP-khó, và NP-đầy đủ, Jason làm cho tuyên bố rằng
các vấn đề ngăn chặn là vấn đề NP-hard cổ điển. Đây là vấn đề đưa ra một chương trình P và đầu vào I, nó sẽ dừng lại? Đây là một vấn đề quyết định nhưng nó không nằm trong NP. Rõ ràng là bất kỳ vấn đề NP-complete nào cũng có thể được giảm xuống mức này.
Mặc dù tôi đồng ý rằng vấn đề dừng lại là vấn đề "khó khăn" hơn bất kỳ thứ gì trong NP, tôi thực sự không thể đưa ra bằng chứng chính thức, toán học rằng sự cố tạm dừng là NP-hard. Đặc biệt, tôi dường như không thể tìm thấy một ánh xạ nhiều đối một thời gian đa thức từ các trường hợp của mọi vấn đề trong NP (hoặc ít nhất, bất kỳ vấn đề NP-complete đã biết) nào về vấn đề dừng.
Có bằng chứng đơn giản nào cho thấy sự cố tạm dừng là NP-hard không?
Cảm ơn rất nhiều! Tôi đã bỏ lỡ bước trung gian giới thiệu TM giải quyết vấn đề. – templatetypedef
Sự cố tạm dừng nổi tiếng là không thể giải quyết được, vậy làm cách nào để có một thuật toán quyết định trong thời gian NP-complete? – djhaskin987
@ djhaskin987 Vấn đề dừng không phải là NP-hoàn chỉnh (bởi vì, như bạn lưu ý, nó không phải là decidable do đó không phải trong NP), nhưng nó là NP-cứng (có nghĩa là, ít nhất là cứng như tất cả mọi thứ trong NP sau một đa thức- giảm thời gian) vì mọi vấn đề quyết định đều có thể giảm xuống. –