DAA - Định lý Cook
Stephen Cook đã trình bày bốn định lý trong bài báo của ông “Sự phức tạp của các thủ tục chứng minh định lý”. Các định lý này được nêu dưới đây. Chúng tôi hiểu rằng nhiều thuật ngữ chưa biết đang được sử dụng trong chương này, nhưng chúng tôi không có bất kỳ phạm vi nào để thảo luận mọi thứ một cách chi tiết.
Sau đây là bốn định lý của Stephen Cook:
Định lý-1
Nếu một bộ S chuỗi được chấp nhận bởi một số máy Turing không xác định trong thời gian đa thức, sau đó S P có thể rút gọn thành {DNF tautologies}.
Định lý-2
Các tập sau đây có thể rút gọn P thành từng cặp (và do đó mỗi tập có cùng mức độ khó đa thức): {tautologies}, {DNF tautologies}, D3, {cặp biểu đồ con}.
Định lý-3
Bất cứ gì TQ(k) thuộc loại Q, $ \ mathbf {\ frac {T_ {Q} (k)} {\ frac {\ sqrt {k}} {(log \: k) ^ 2}}} $ không bị giới hạn
Đây là một TQ(k) thuộc loại Q sao cho $ T_ {Q} (k) \ leqslant 2 ^ {k (log \: k) ^ 2} $
Định lý-4
Nếu tập chuỗi S được chấp nhận bởi một máy không xác định trong thời gian T(n) = 2n, và nếu TQ(k) là một hàm trung thực (tức là có thể đếm được trong thời gian thực) của loại Q, sau đó có một hằng số K, vì thế S có thể được công nhận bởi một máy xác định trong thời gian TQ(K8n).
Đầu tiên, ông nhấn mạnh tầm quan trọng của tính rút gọn thời gian đa thức. Có nghĩa là nếu chúng ta giảm thời gian đa thức từ bài toán này sang bài toán khác, điều này đảm bảo rằng bất kỳ thuật toán thời gian đa thức nào từ bài toán thứ hai đều có thể được chuyển đổi thành thuật toán thời gian đa thức tương ứng cho bài toán đầu tiên.
Thứ hai, ông tập trung chú ý vào NP lớp của các bài toán quyết định có thể được giải quyết trong thời gian đa thức bằng một máy tính không xác định. Hầu hết các vấn đề khó chữa thuộc về lớp này, NP.
Thứ ba, ông đã chứng minh rằng một bài toán cụ thể trong NP có tính chất mà mọi bài toán khác trong NP đều có thể được rút gọn thành nó. Nếu bài toán thỏa mãn có thể được giải bằng thuật toán thời gian đa thức, thì mọi bài toán trong NP cũng có thể được giải trong thời gian đa thức. Nếu bất kỳ vấn đề nào trong NP là khó giải quyết, thì vấn đề thỏa mãn phải là khó chữa. Vì vậy, vấn đề thỏa mãn là vấn đề khó nhất ở NP.
Thứ tư, Cook gợi ý rằng các vấn đề khác trong NP có thể đồng nghĩa với vấn đề thỏa mãn tính chất là thành viên khó khăn nhất của NP này.