Độ phức tạp tính toán, P và NP

SAT rõ ràng thuộc NP: một phép gán thỏa mãn là một chứng chỉ có thể kiểm tra trong thời gian đa thức chỉ bằng cách thay giá trị vào. Phần sâu sắc là chứng minh mọi bài toán NP đều quy dẫn về SAT — điều này đúng vì một công thức Boolean đủ biểu cảm để mô tả, từng bước một, toàn bộ quá trình chạy của bất kỳ bộ kiểm chứng thời gian đa thức nào, từng ô nhớ và từng thời điểm, nên "có tồn tại chứng chỉ hay không" trở thành "công thức khổng lồ này có thỏa mãn được không".

Cho $A \in NP$ với bộ kiểm chứng thời gian đa thức $V$ chạy trong thời gian nhiều nhất $n^k$ trên đầu vào độ dài $n$ kèm một chứng chỉ độ dài nhiều nhất $n^k$. Cố định một đầu vào $x$ độ dài $n$; ta xây một công thức Boolean $\phi_x$, thỏa mãn được đúng khi có một chứng chỉ nào đó làm $V$ chấp nhận.

Hãy tưởng tượng toàn bộ quá trình tính toán của $V$ trên $(x,y)$, với chứng chỉ $y$ chưa biết, được trình bày như một bảng (tableau): một lưới $n^k \times n^k$ trong đó hàng $t$ ghi lại toàn bộ nội dung băng và vị trí đầu đọc của bộ kiểm chứng tại bước thời gian $t$. Đưa vào một biến Boolean cho mỗi bộ ba (ô, bước thời gian, ký hiệu có thể), ghi lại ký hiệu nào nằm ở ô đó tại thời điểm đó — vì lưới có số ô và số bước thời gian là đa thức, đây là một số lượng biến đa thức.

Công thức $\phi_x$ được xây dựng như một phép hội (AND) các mệnh đề áp đặt bốn điều kiện cục bộ, dễ kiểm tra: (1) mỗi ô chứa đúng một ký hiệu tại mỗi bước thời gian; (2) hàng $0$ mã hóa đúng đầu vào cố định $x$ theo sau là chỗ trống cho chứng chỉ $y$ chưa được đoán; (3) mỗi cửa sổ nhỏ gồm các ô liền kề qua hai bước thời gian liên tiếp nhất quán với quy tắc chuyển trạng thái của $V$ (đây là nơi các bit chứng chỉ, để tự do ở hàng $0$, được phép ảnh hưởng tới phần còn lại của tính toán); (4) một ô nào đó tại bước thời gian cuối cùng ghi lại trạng thái chấp nhận.

Mỗi điều kiện trên chỉ ràng buộc một vùng lân cận nhỏ, cỡ cố định của các biến, nên mỗi điều kiện chuyển thành một số mệnh đề hằng số, và chỉ có số lượng đa thức vùng lân cận cần ràng buộc — nên $\phi_x$ có kích thước đa thức và tính được từ $x$ trong thời gian đa thức. Theo cách xây dựng, $\phi_x$ thỏa mãn được đúng khi tồn tại một bảng nhất quán, tức là đúng khi có chứng chỉ $y$ nào đó làm $V(x,y)$ chấp nhận, tức là đúng khi $x \in A$. Điều này thể hiện phép quy dẫn $A \le_p \text{SAT}$ cho một $A \in NP$ bất kỳ, kết hợp với $\text{SAT} \in NP$ đã chỉ ra ở trên, chứng minh SAT là NP-đầy đủ.

Tính NP-đầy đủ của $B$ nghĩa là mọi bài toán NP đều có thể được viết lại, trong thời gian đa thức, thành một thể hiện của $B$. Nếu bản thân $B$ sau đó có thể giải trong thời gian đa thức, việc nối bước viết lại và bước giải lại với nhau cũng giải được bài toán NP gốc trong thời gian đa thức — nên chỉ một bài toán NP-đầy đủ khả thi sẽ kéo mọi bài toán NP xuống P cùng với nó.

Giả sử $B$ là NP-đầy đủ và có một thuật toán giải $B$ trong thời gian $O(n^{k_1})$. Lấy bất kỳ $A \in NP$; theo tính NP-đầy đủ của $B$, $A \le_p B$, nghĩa là tồn tại một hàm quy dẫn $f$ tính được trong thời gian $O(n^{k_2})$ biến các thể hiện của $A$ thành thể hiện của $B$ trong khi bảo toàn đáp án có/không.

Với một đầu vào $x$ độ dài $n$ của $A$, trước tiên tính $f(x)$: việc này mất thời gian $O(n^{k_2})$, và đặc biệt đầu ra $f(x)$ có độ dài nhiều nhất $O(n^{k_2})$ (một thuật toán thời gian đa thức không thể viết ra nhiều đầu ra hơn thời gian nó chạy). Sau đó chạy thuật toán thời gian đa thức cho $B$ trên $f(x)$: vì $|f(x)| = O(n^{k_2})$, việc này mất thời gian $O\big((n^{k_2})^{k_1}\big) = O(n^{k_1 k_2})$.

Tổng thời gian chạy là $O(n^{k_2}) + O(n^{k_1 k_2}) = O(n^{k_1 k_2})$, vẫn là một đa thức theo $n$ (hợp của hai đa thức là một đa thức). Theo tính đúng đắn của phép quy dẫn, $x$ là thể hiện có đáp án "có" của $A$ khi và chỉ khi $f(x)$ là thể hiện có đáp án "có" của $B$, nên thủ tục kết hợp này quyết định đúng $A$ trong thời gian đa thức.

Vì $A \in NP$ là bất kỳ, mọi bài toán NP đều có một thuật toán thời gian đa thức, tức $NP \subseteq P$. Kết hợp với bao hàm luôn đúng $P \subseteq NP$, ta có $P = NP$.