Định lý Cook–Levin
Phát biểu
Bài toán thỏa mãn Boole (SAT) là NP-đầy đủ: SAT thuộc lớp NP, và mọi ngôn ngữ trong NP đều quy dẫn được về SAT trong thời gian đa thức. Do đó, nếu SAT giải được trong thời gian đa thức thì P = NP.
Vì sao đúng?
Các bài toán NP chính là những bài toán mà lời giải đề xuất có thể kiểm tra nhanh, dù việc tìm ra nó có thể khó. SAT — quyết định xem một công thức Boole có thể làm cho đúng hay không — trông như chỉ là một câu đố cụ thể trong vô số câu đố, nhưng hóa ra nó là một 'bộ phiên dịch vạn năng': quá trình tính toán của bất kỳ bộ kiểm tra thời gian đa thức nào, kiểm tra bất kỳ lời giải đề xuất nào cho bất kỳ bài toán NP nào, đều có thể mã hóa từng bước thành một công thức Boole thỏa mãn được đúng khi tồn tại lời giải hợp lệ. Vì vậy SAT khó ít nhất bằng mọi bài toán trong NP.
Phác thảo chứng minh
Với ngôn ngữ bất kỳ , cố định máy Turing của bộ kiểm tra thời gian đa thức và một chặn đa thức cho thời gian chạy. Mã hóa toàn bộ quá trình tính toán của máy trên đầu vào độ dài thành một lưới lớn các biến Boole ghi lại, tại mỗi bước thời gian và mỗi ô băng, ký hiệu được ghi, vị trí đầu đọc, và trạng thái máy. Các mệnh đề buộc: đúng một ký hiệu/trạng thái cho mỗi ô/bước, cấu hình khởi tạo đúng, quy tắc chuyển đúng giữa các bước liên tiếp, và đạt trạng thái chấp nhận vào cuối. Hội các mệnh đề này thỏa mãn được đúng khi tồn tại một tính toán chấp nhận, tức đúng khi đầu vào thuộc , và kích thước của nó là đa thức theo , cho ra một quy dẫn thời gian đa thức từ về SAT.
Người phát biểu
Người chứng minh
Chủ đề chứa định lý này
Định lý liên quan
Chứng minh từng bước
Chưa có chứng minh từng bước cho định lý này.
Tài liệu tham khảo
- Stephen A. Cook (1971). The complexity of theorem-proving procedures
- Michael R. Garey, David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness