các vấn đề NP-complete đầu tiên được hiển thị là NP-complete như thế nào?

Question

Từ mục nhập wikipedia trên NP-Complete:

"Cách dễ nhất để chứng minh rằng một số vấn đề mới NP-complete trước tiên phải chứng minh rằng đó là NP, sau đó giảm một số vấn đề NP-complete đã biết nó"

tôi khá chắc chắn rằng tôi hiểu được điều này: Nếu tôi có một vấn đề, tôi có thể chứng minh rằng nó là NP-đầy đủ nếu tôi:

1. chứng minh rằng nó là trong NP (một giải pháp tới sự cố có thể được xác minh trong thời gian đa thức trên không -deterministic máy Turing)

2. Chứng tỏ rằng một vấn đề đã được biết đến là NP-đầy đủ có thể được 'giảm' cho vấn đề mới

Vì vậy, câu hỏi của tôi là, làm thế nào là NP- đầu tiên hoàn thành các vấn đề 'đã được chứng minh' để được NP-hoàn thành? Tại một thời điểm, tập hợp các vấn đề NP-complete đã biết phải là số không, và điều này sẽ làm cho nó không thể chuyển sang bước 2 trong quá trình trên.

Điều này làm cho tôi nghĩ rằng có một phương pháp khác để chứng minh mà tôi không biết. Hoặc là, hoặc có thể toàn bộ NP-tài sản hoàn thành là 'giả định' cho các vấn đề nhất định do thiếu một giải pháp thời gian đa thức được biết đến. (thực ra, khi viết bài này, tôi sẽ không ngạc nhiên nếu đây là trường hợp, nhưng tôi cũng muốn một số phản hồi của guru).

Answer 1

Cook's Theorem

Các NP lớp có thể được định nghĩa là lớp của các vấn đề decidable bởi một máy Turing không xác định trong thời gian đa thức. Định lý này cho thấy rằng SAT là NP-complete bằng cách mã hóa hoạt động của bất kỳ máy Turing không xác định nào bằng công thức boolean, theo cách mà máy chấp nhận nếu và chỉ khi công thức đó là SATisfiable.

Trong lịch sử nói, khái niệm về NP-đầy đủ đã được giới thiệu trong bài báo Richard Karp của tinh (Reducibility Among Combinatorial Problems), nơi ông định nghĩa NP-đầy đủ, sử dụng định lý Cook, và trong một shot lớn, tỏ ra 21 vấn đề NP-đầy đủ.

Answer 2

Để cung cấp cho bạn những tinh hoa của các bằng chứng (đó là một vài trang khó đi trong Garey & Johnson Máy tính và Intractibility):

Bất kỳ vấn đề tính toán có thể được diễn tả như một máy Turing.

Có thể diễn tả máy Turing như một vấn đề logic, đáp ứng một số hạn chế phức tạp nhất định.

Vì vậy, nếu bạn có thể giải quyết vấn đề logic trong thời gian đa thức, bạn có thể giải quyết vấn đề về máy Turing trong thời gian đa thức.

Điều này (cùng với một số cân nhắc khác) cho thấy rằng nếu bạn có thể giải quyết vấn đề logic trong thời gian đa thức, bạn có thể giải quyết bất kỳ vấn đề NP nào trong thời gian đa thức. Đây là định nghĩa của NP-hoàn chỉnh, vấn đề logic là do đó NP-hoàn thành, và có thể được sử dụng như là một cơ sở cho các vấn đề khác.

Vấn đề logic được sử dụng được gọi là Sự hài lòng (thường được viết tắt là SAT). Đưa ra một loạt mệnh đề của biểu mẫu (A hoặc không B hoặc không-C) (mệnh đề bao gồm bất kỳ số mệnh đề và phủ định nào của mệnh đề được kết nối bằng lôgíc hoặc), có gán giá trị chân lý cho các mệnh đề các mệnh đề đúng?

NP-đầy đủ là thuộc tính được xác định rõ. Lý do duy nhất bạn nghi ngờ về một vấn đề là NP-complete là bạn nghĩ rằng bạn có thể giảm một vấn đề NP-complete khác cho nó, nhưng không quản lý để tìm một vấn đề thuận tiện hoặc lấy được một bằng chứng được nêu ra.

Câu hỏi đặt ra là liệu các vấn đề NP-complete tồn tại hay cách chứng minh một vấn đề là NP-complete, nhưng điều đó có nghĩa là gì. Chưa có ai tạo ra một thuật toán đa thức thời gian để giải quyết một vấn đề NP-complete, và không ai chứng minh rằng một thuật toán như vậy không thể tồn tại. Có hay không P = NP, chúng tôi chắc chắn không có thuật toán tốt để giải quyết bất kỳ vấn đề NP-hoàn thành.

Đây là một trong những vấn đề về Millenium của Quỹ Claypool, vì vậy nếu bạn có thể đưa ra bằng chứng cho thấy một số người rất thông minh trong một vài năm, bạn sẽ nhận được một triệu đô la.