Tiểu luận môn Lý thuyết tính toán Bài toán có giới hạn điều kiện
Trong mục này chúng ta đi chứng minh một loạt các bài toán như: bài toán TSP
được trình bày trong phần 10.1.4, là NP-đầy đủ. Về nguyên tắc, chúng ta làm như
vậy bằng cách tìm sự giảm thời gian theo đa thức từ bài toán SAT cho mỗi vấn đề
quan tâm. Tuy nhiên, có một bài toán trung gian quan trọng, được gọi là "3SAT"
dễ hơn nhiều so với SAT để giảm các bài toán mẫu. 3SAT vẫn là bài toán về sự
thỏa mãn các biểu thức logic, nhưng những biểu thức này có dạng rất phổ biến:
AND của "mệnh đề", OR “biến” hoặc “biến phủ định”.
Trong phần này sẽ trình bày một số thuật ngữ quan trọng về biểu thức logic. Sau
đó ta đơn giản điều kiện cho mọi biểu thức để thỏa với các biểu thức ở dạng chuẩn
3SAT. Ta thấy rằng trong mỗi biểu thức logic E luôn có biểu thức tương đương F ở
dạng chuẩn của 3SAT, kích cở của F có thể là theo cấp số nhân kích cở của E. Vì
vậy, để giảm thời gian đa thức của SAT để 3SAT tối ưu hơn các thao tác đại số
logic đơn giản. Ta cần chuyển đổi biểu thức E trong SAT thành biểu thức F ở dạng
chuẩn 3SAT. Tuy nhiên, F không nhất thiết phải tương đương với E. Chúng ta
chắc chắn rằng F thỏa mãn nếu và chỉ nếu E đúng.
10.3.1 Hình thức chuẩn cho biểu thức logic
Sau đây là 3 định nghĩa:
• Chữ A là một biến hoặc biến phủ định. Ví dụ x và ¬ y. Ta thường sử dụng
y
để
thay thế cho ¬ y.
• Mệnh đề A là OR hoặc AND của nhiều biến. Ví dụ là x, x ∨ y, và x ∨
y
∨ z.
• Một biểu thức logic được cho là ở dạng chuẩn hội hay CNF, nếu nó AND các
mệnh đề.
Để rút gọn các biểu thức, chúng ta dùng ký hiệu thay thế như ∨ là tổng thay
cho toán tử +, và ∧ là tích. Đối với tích, ta viết liền nhau, tức là không dùng toán tử
∧.
Ví dụ 10.10: Biểu thức (x ∨

), (x + y + z),
và (
y
+
z
) là dạng 2-CNF, bởi vì mỗi mệnh đề có đúng 2 biến.
Tất cả giới hạn này trong biểu thức logic tạo ra một số bài toán riêng của
chúng mà thỏa mãn biểu thức giới hạn. Vì vậy, ta xem xét các bài toán sau đây:
• Bài toán CSAT: cho một biểu thức logic ở dạng CNF, nó có thỏa mãn không?
• Bài toán fcSAT: cho biểu thức logic là k-CNF, nó có thỏa mãn hay không?
Ta thấy rằng CSAT, 3SAT, và kSAT với mọi k lớn hơn 3 là NP-đầy đủ. Tuy nhiên,
có thuật toán mất thời gian tuyến tính để giải 1SAT và 2SAT.
10.3.2 Chuyển đổi biểu thức sang dạng CNF
Hai biểu thức logic được cho là tương đương nếu chúng có cùng một kết quả với
bất kỳ giá trị của các biến trong biểu thức. Nếu hai biểu thức là tương đương, thì
2
Xử lý đầu vào lỗi
Mỗi bài toán đã trình bày - SAT, CSAT, 3SAT,… - là ngôn ngữ
trên bảng chữ cái 8-ký tự cố định, đôi khi ta có thể xem như các biểu
thức logic. Một chuỗi không có thể dịch được là một biểu thức tồn tại
trong ngôn ngữ SAT. Tương tự như vậy, khi ta xem xét biểu thức giới
hạn, một chuỗi được tạo ra ở dạng biểu thức logic đúng, nhưng không
phải là biểu thức ở của người dùng đặt ra, không phải là ngôn ngữ. Như
vậy, thuật toán quyết định cho bài toán CSAT, Chằng hạn, nói "không"
nếu đưa ra biểu thức logic là thỏa mãn, nhưng nó không phải CNF.
chắc chắn hoặc là cả hai đều thỏa mãn hay không thỏa mãn. Vì vậy, chuyển đổi
biểu thức bất kỳ thành biểu thức CNF tương đương là cách tiếp cận để làm giảm
thời gian phi tuyến tính từ SAT thành CSAT. Sự giảm đó xác nhận CSAT là NP-
đầy đủ.
Tuy nhiên, mọi thứ không hoàn toàn đơn giản như vậy. Trong khi ta có thể

3.¬ (¬ (E)) => E. Luật phủ định hai lần
Định lý 10.11: Mỗi biểu thức logic E tương đương với biểu thức F, trong đó các
biến đều phủ định. Hơn nữa, chiều dài của F là tuyến tính theo số lượng biểu
tượng của E và F có thể được xây dựng từ E mất thời gian phi tuyến tính.
Chứng minh: Dùng phương pháp quy nạp trên số lượng toán tử (∧, ∨, và ¬). Ta
đưa ra một biểu thức tương đương F có ¬’s các biến, hơn nữa nếu E có ≥ 1 toán tử
thì F không có nhiều hơn 2n – 1 toán tử.
Vì F không cần có nhiều hơn một cặp dấu ngoặc đơn cho toán tử, và số lượng biến
trong một biểu thức không vượt quá số lượng toán tử một lần, ta kết luận rằng độ
dài của F là tuyến tính tỷ lệ thuận với độ dài của E. Quan trọng hơn, ta thấy rằng,
vì xây dựng F khá đơn giản, thời gian cần để xây dựng F tỷ lệ thuận với chiều dài
của nó, do đó tỷ lệ thuận với độ dài của E.
Cơ sở: Nếu F có một toán tử, thuộc các dạng ¬x, x ∨ y, hay x ∧ y cho các biến x
và y. Trong mỗi trường hợp, E tồn tại ở dạng đã cho, vậy F = E. Lưu ý rằng, vì E
và F chỉ có một toán tử. F có nhiều nhất bằng hai lần toán tử của E trừ đi cho 1
Quy nạp: Giả sử phát biểu trên là đúng cho tất cả biểu thức có ít toán tử hơn E.
Nếu toán tử đầu của E là ¬, E có dạng E1 ∨ E2 hoặc E1 ∧ E2. Trong cả hai trường
4
hợp, giả thuyết quy nạp áp dụng cho E1 và E2 có biểu thức tương đương F1 và F2.
F = F1 ∨ F2 hoặc F = F1 ∧ F2 là một tương đương thỏa mãn E. E1 và E2 có a và b
toán tử. Thì E có a + b + 1 toán tử. Giả thuyết quy nạp, F1 và F2 có nhiều nhất 2a -
1 và 2b - 1 toán tử. Như vậy, F có nhiều nhất là 2a + 2b - 1 toán tử, không quá 2 (a
+ b +1) - 1, hay hai lần số lượng các toán tử của E trừ đi 1.
Bây giờ, xem xét trường hợp E có dạng ¬E1. Có ba trường hợp, tùy thuộc vào toán
tử đầu tiên của E1. Lưu ý rằng E1 phải có một toán tử, hay E là một trường hợp cơ
bản.
1. E1 = ¬E2 Luật phủ định kép, E = ¬(¬ E2) tương đương với E2. Vì E2 có ít toán
tử hơn E, giả thuyết quy nạp được áp dụng. Chúng ta có thể tìm thấy F tương
đương E2 trong đó ¬’s là các biến. Vì số lượng toán tử của F nhiều nhất là hai lần
của E2 trừ đi 1, chắc chắn không quá hai lần số toán tử của E trừ đi 1.

trình bày, để hình thành biểu thức F từ E với thời gian đa thức thỏa mãn nếu và chỉ
nếu E thỏa mãn, ta phải loại bỏ sự chuyển đổi duy trì tính tương đương, và đưa ra
một số biến mới cho F mà không xuất hiện trong E. Ta đưa ra "bẫy" bằng chứng
của định lý CSAT là NP-đầy đủ, và sau đó cho một ví dụ về bẫy để xây dựng rõ
ràng hơn.
Định lý 10.13: CSAT là NP-đầy đủ.
Chứng minh: Ta trình bày làm thế nào để chuyển SAT thành CSAT theo thời gian
đa thức. Đầu tiên, sử dụng định lý 10.12 để chuyển đổi ví dụ đã cho SAT sang biểu
thức E mà ¬ 's chỉ có các biến. Sau đó, ta trình bày cách chuyển đổi E thành CNF
trong thời gian đa thức và thấy rằng F thỏa mãn nếu và chỉ nếu E đúng. Việc xây
dựng F dùng phương pháp quy nạp trên độ dài của E. Các thuộc tính đặc biệt mà F
có nhiều hơn chúng ta cần. Chính xác, chúng ta trình bày bằng quy nạp số lần xuất
hiện biểu tượng ("chiều dài") E:
a)F là CNF, và bao gồm nhiều mệnh đề n nhất.
b) F xây dựng từ E trong thời gian lớn nhất là c|E|
2
.
6
c)Một phép gán T cho E làm E đúng nếu và chỉ nếu tồn tại phần mở rộng S của
T mà làm cho F đúng.
Cơ sở: Nếu E gồm một hoặc hai biến. Biến A là một mệnh đề, vậy E là CNF.
Phương pháp quy nạp: Giả sử rằng mỗi biểu thức nhỏ hơn E có thể được chuyển
đổi thành tích của các mệnh đề, và chuyển đổi này tốn nhiều nhất cn
2
thời gian trên
biểu thức của chiều dài n. Có hai trường hợp, tùy thuộc vào toán tử đầu tiên của E.
Trường hợp 1: E = E1 ∧ E2, giả thuyết quy nạp, biểu thức F1 và F2 được tính từ
E1 và E2 là CNF. Chúng thỏa mãn phép gán E1, có thể thỏa F1, tương tự cho E2
và F2. Ta giả định rằng các biến F1 và F2 riêng biệt, trừ những biến xuất hiện
trong E, tức là, nếu ta đưa các biến vào F1 hoặc F2, sử dụng các biến riêng biệt.

Thì T1 mà T giới hạn các biến của E1, có thể được mở rộng đến S1, thỏa F1. Xây
dựng phần mở rộng S cho T như sau: S sẽ thỏa biểu thức F được định nghĩa ở trên:
1. Đối với tất cả các biến x trong F, S (x) = S1(x).
2.S(y) = 0. Lựa chọn này làm cho tất cả các mệnh đề của F được mở rộng F2
đúng.
3.Đối với tất cả các biến x trong F2 nhưng không trong Fx, S(x) là T(x) nếu sau
này được xác định, và nếu không có thể là 0 hoặc 1
Sau đó S làm tất cả các mệnh đề từ g’s đúng vì quy tắc 1. S làm tất cả các mệnh đề
từ h’s đúng theo quy tắc 2 – gán cho y. Như vậy, S thỏa mãn F.
Nếu T không thỏa E1, nhưng thỏa E2, thì tham số giống nhau, ngoại trừ S(y) = 1
theo quy tắc 2. Ngoài ra, S(x) phải thỏa với S2(x) bất cứ khi nào S2(x) được định
nghĩa, nhưng S(x) chỉ xuất hiện trong S1 bất kỳ. Chúng ta kết luận rằng trong
trường hợp này S thỏa mãn F.
Giả sử rằng gán T cho E được mở rộng để gán S cho F và S thỏa mãn F. Có hai
trường hợp, tùy thuộc vào những gì giá trị thật được gán cho y. Đầu tiên giả sử
rằng S(y) = 0. Thì tất cả các mệnh đề của F xuất phát từ h’s đúng. Tuy nhiên, y
không hỗ trợ mệnh đề có dạng (y + gi) xuất phát từ g’s, đều này có nghĩa là S đúng
với mỗi giá trị g’s, S làm cho F1 đúng.
Chính xác hơn, để S1 bị S hạn chế đến các biến F1. Thì S1 thỏa mãn F1. Bằng giả
thuyết quy nạp, T1, mà bị T hạn chế đến các biến của E1, phải thỏa mãn Ex. Vì S1
là phần mở rộng của T1. Nên từ T1 thỏa mãn F1, T thỏa mãn E, đó là E1 ∨ E2.
Chúng ta cũng phải xem xét trường hợp S(y) = 1, nhưng trường hợp này là đối
xứng với kết quả ta đã nêu. Chúng ta kết luận rằng T thỏa mãn E bất cứ khi nào S
thỏa mãn F.
Bây giờ, chúng ta xem xét thời gian để xây dựng F từ E là bậc nhất theo n, n chiều
dài của E. Bất kể trường hợp này áp dụng tách rời E thành E1 và E2, và xây dựng
F từ F1 và F2. Đặt dn là ràng buộc trên về thời gian để xây dựng E1 và E2 từ E
9
cộng với thời gian xây dựng F từ F1 và F2. Có một phương trình tái phát cho T(n),
thời gian để xây dựng F từ bất kỳ E theo chiều dài n, dạng của nó là:

2
- n, với mọi i trong phạm vi cho phép. Theo quy tắc đệ
quy trong định nghĩa của T(n) thì T (n) ≤ dn + cn
2
- cn. Nếu chúng ta chọn c ≥ d,
chúng ta có thể suy ra rằng T (n)< cn
2
với mọi n. Vì vậy, việc xây dựng F từ E mất
thời gian 0(n
2
).
10
Ví dụ 10.14: Dùng định lý 10.13 để áp dụng cho một biểu thức đơn giản: E = x
y
+
x
(y + z). Hình 10.7 cho thấy các phân tích cú pháp của biểu thức này. Mỗi nút là
biểu thức CNF.
Hình 10.7
Biểu thức CNF là một mệnh đề chỉ có một ký tự. Ví dụ, chúng ta thấy rằng nút lá
được gán ký tự
y
có biểu thức CNF liên quan (
y
). Các dấu ngoặc đơn là không
cần thiết, nhưng chúng ta đặt chúng trong các biểu thức CNF giúp nhắc nhở rằng
chúng ta đang nói về tích của các mệnh đề.
Đối với nút AND, xây dựng biểu thức CNF một cách đơn giản để tính tích (AND)
của các mệnh đề cho hai biểu thức con. Vì vậy, ví dụ, nút biểu thức con
x

), đây là
phần đầu của E. Tuy nhiên, ta có thể chọn một trong hai giá trị cho v, vì trong biểu
thức con y + z, cả hai bên toán tử OR đúng theo T.
10.3.4 NP-Tính đầy đủ của 3SAT
Bây giờ, ta trình bày lớp biểu thức logic chẵn nhỏ hơn bài NP-đầy đủ thỏa mãn bài
toán. Lấy lại bài toán 3SAT là:
• Cho một biểu thức logic E là tích của các mệnh đề, mỗi mệnh đề là tổng của ba
biến riêng biệt, vậy E có thỏa mãn không?
Mặc dù các biểu thức 3-CNF là một phần nhỏ của biểu thức CNF, rất phức tạp để
kiểm tra sự thỏa mãn NP-đầy đủ, như các định lý tiếp theo.
Định lý 10.15: 3SAT là NP-đầy đủ.
Chứng minh: Rõ ràng 3SAT thuộc NP, vì SAT thuộc NP. Để chứng minh NP-đầy
đủ, ta chuyển đổi CSAT thành 3SAT. Sự chuyển đổi như sau. Cho biểu thức CNF
E = e1 ∧ e2 ∧… ∧ ek, ta thay mỗi mệnh đề ei như sau, để tạo ra biểu thức mới F.
thời gian để xây dựng F là tuyến tính theo chiều dài của E, và thấy rằng phép gán
thỏa mãn E khi và chỉ khi nó được triển khai thỏa mãn phép gán cho F.
1. Nếu ei là một biến đơn, như (x). Ta đưa ra hai biến mới u và v. Thay thế (x) vào
bốn mệnh đề (x + u + v)(x + u + v)(x + u + v)(x + u + v). Vì u và v có trong 4
mệnh đề, cách duy nhất để thỏa mãn bốn mệnh đề là làm x đúng. Như vậy, tất cả
thỏa mãn các phép gán cho E được triển khai để thỏa mãn cho F.
2.Giả sử ei là tổng của hai biến, (x + y). Ta đưa ra một biến mới z, và thay thế e,
vào tích của hai mệnh đề (x + y + z)(x + y + z). Như trong trường hợp 1, cách duy
nhất để thảo mãn cả hai mệnh đề là phảo thỏa mãn (x + y).
12
3. Nếu là tổng của ba biến, như ở dạng của 3-CNF, vì vậy ta loại bỏ ei trong biểu
thức F đang được xây dựng.
4. Giả sử ei = (x1 + x2 + + xm) với m ≥ 4. Ta đưa ra các biến mới y1, y2, ym-3 và
thay thế ei vào tích của các mệnh đề
Một phép gán T mà thỏa mãn E phải làm cho ít nhất một biến của ei đúng, ta nói
rằng nó làm cho xj đúng ( xj là biến hay biến phủ định). Để thuận tiện, ta chúng là

sai. Bắt đầu bằng giả định một biến đúng, và suy ra những kết quả cho các biến
khác.
14