Bài viết này sẽ đi sâu vào một biến thể thú vị của bài toán thỏa mãn Boolean, được gọi là 1-or-3-in-3-SAT (đôi khi còn được gọi là odd-3-SAT). Chúng ta sẽ khám phá độ phức tạp của bài toán này và tìm hiểu lý do tại sao, một cách đáng ngạc nhiên, nó có thể được giải quyết trong thời gian đa thức. Bài viết này sẽ hữu ích cho bất kỳ ai quan tâm đến lý thuyết độ phức tạp tính toán, đặc biệt là những người đang nghiên cứu về các bài toán NP-hard và các thuật toán hiệu quả.
Trong bài toán thỏa mãn Boolean (SAT), chúng ta có một công thức Boolean, thường ở dạng chuẩn hội (CNF), và nhiệm vụ là tìm một phép gán giá trị cho các biến để công thức đó đúng. Bài toán 1-or-3-in-3-SAT là một biến thể của 3-SAT, trong đó mỗi mệnh đề chứa chính xác ba literal (một biến hoặc phủ định của nó). Yêu cầu của 1-or-3-in-3-SAT là tìm một phép gán sao cho mỗi mệnh đề chứa *một hoặc ba* literal đúng. Điều này khác với 3-SAT thông thường, vốn chỉ yêu cầu mỗi mệnh đề có *ít nhất một* literal đúng.
Ví dụ, xét mệnh đề (x ∨ ¬y ∨ z). Trong 1-or-3-in-3-SAT, chúng ta cần một phép gán sao cho hoặc chỉ x đúng, hoặc chỉ ¬y đúng, hoặc chỉ z đúng, hoặc cả x, ¬y và z đều đúng. Các trường hợp khác đều không được chấp nhận.
Điều thú vị là, mặc dù là một biến thể của 3-SAT (vốn là một bài toán NP-hard), 1-or-3-in-3-SAT lại thuộc lớp PTIME (có thể giải quyết trong thời gian đa thức). Điều này có nghĩa là có một thuật toán có thể giải bài toán này trong thời gian chấp nhận được, ngay cả với các trường hợp lớn.
Bí quyết nằm ở việc chuyển đổi bài toán thành một hệ phương trình tuyến tính trên trường Z2 (modulo 2). Cụ thể, chúng ta có thể biểu diễn mỗi mệnh đề 1-or-3-in-3 bằng một phương trình XOR (exclusive OR).
Xét một mệnh đề C, gọi k là số lượng literal bị phủ định trong C. Khi đó, mệnh đề C đúng nếu và chỉ nếu tổng (theo modulo 2) của các biến (không phải literal!) được gán giá trị true, cộng với k, là lẻ. Ví dụ, mệnh đề (x, ¬y, z) có một phép phủ định, vì vậy nó đúng nếu có một số chẵn các biến x, y, z đúng – không quan trọng biến nào.
Mệnh đề (x ∨ ¬y ∨ z) tương đương với phương trình x + y + z = 0 (mod 2). Một hệ phương trình tuyến tính modulo 2 có thể được giải bằng phương pháp khử Gaussian trong thời gian đa thức.
Giả sử chúng ta có công thức:
Chúng ta có thể chuyển đổi nó thành hệ phương trình:
Giải hệ này bằng phép khử Gauss (Gaussian elimination) sẽ cho chúng ta một nghiệm (nếu có) trong thời gian đa thức.
Bài toán 1-or-3-in-3-SAT còn được gọi là XORSAT, vì nó liên quan đến các phép toán XOR. **Định lý Schaefer** là một kết quả quan trọng trong lý thuyết độ phức tạp, cung cấp một sự phân đôi cho các bài toán thỏa mãn Boolean tổng quát. Nó nói rằng bất kỳ bài toán nào như vậy, thỏa mãn một số điều kiện nhất định, hoặc là thuộc lớp P (giải được trong thời gian đa thức) hoặc là NP-hard. XORSAT là một trong những trường hợp có thể giải được trong thời gian đa thức theo định lý này.
Bài toán 1-or-3-in-3-SAT là một ví dụ điển hình về việc độ phức tạp của một bài toán có thể thay đổi đáng kể, ngay cả khi chỉ có một sự thay đổi nhỏ trong định nghĩa của nó. Mặc dù 3-SAT là NP-hard, 1-or-3-in-3-SAT lại có thể giải được trong thời gian đa thức nhờ vào việc chuyển đổi nó thành một hệ phương trình tuyến tính. Điều này nhấn mạnh tầm quan trọng của việc phân tích kỹ lưỡng cấu trúc của một bài toán trước khi cố gắng giải nó.
Bài viết liên quan