Bài giảng Lý thuyết độ phức tạp - Chương 3: Chứng minh các kết quả của bài toán NP_đầy đủ

Chương 3: Chứng minh các kết quả của bài toán NP_đầy đủ Giảng viên : PSG.TSKH.Vũ Đình Hòa I. Các khái niệm 1.1. Lớp bài toán P (polynomial time) 1.2. Lớp bài toán NP(Nondeterministic polynomial time) 1.3. Quan hệ giữa lớp P và lớp NP II. Các bài toán NP_Complete 2.1. Phép dẫn với thời gian đa thức 2.2. Bài toán NP_Complete (NPC) 2.3. Một số bài toán NPC Chương 3: Chứng minh các kết quả của bài toán NP_đầy đủ I. Các khái niệm 1.1. Lớp bài toán P (polynomial time) Lớp P là lớp bài toán quyết định giải được trong thời gian đa thức trên máy Turing tất định, hay lớp những bài toán dễ (có lời giải chấp nhận được). 1.2. Lớp bài toán NP Là lớp bt quyết định giải được trong thời gian đa thức trên máy Turing không tất định 1.3. Quan hệ giữa lớp P và lớp NP  Ta có thể thấy một cách trực quan là PNP. Nhưng chúng ta vẫn chưa biết P=NP hay không, nhưng hầu hết các nhà nghiên cứu tin rằng P≠NP là sự tồn tại của của lớp bt NPC  Dù chúng ta chưa biết chắc chắn liệu P≠NP song việc chỉ ra được một bài toán là NPC chứng tỏ 1 sự thật là bt đó không thể giải được về phương diện tính toán với thuật toán chính xác, tốt hơn hết là lời giải theo thuật toán gần đúng.  Việc xem xét quan hệ giữa P và NP dẫn đến chúng ta đi đến nghiên cứu lớp NPC II. Các bài toán NP_Comlete (NPC) Phép dẫn với thời gian đa thức Cho hai bài toán 1 và 2. 22 11 2 1 NY NY     2.1 Phép dẫn với thời gian đa thức Phép dẫn thời gian đa thức f biến đổi mỗi dữ kiện 1 thành dữ kiện 2 thỏa mãn : 1. f được thực hiện trong thời gian đa thức 2. Ký hiệu: 1 2 21 21 )( )( NN YY f f     The theory of NP-Completeness 7 Ví dụ : 1 bài toán Chu trình Hamilton Instance: Đồ thị G vô hướng. Question: tồn tại hay không chu trình Hamilton trong G? Ví dụ phép dẫn thời gian đa thức The theory of NP-Completeness 8 Ví dụ: 2 bài toán TST Instance: n, các thành phố: C = {c1, c2,cm}, khoảng cách giữa ci, cj là d(ci, cj)  Z +, B  Z+. Question: Tồn tại hay thỏa : Ví dụ phép dẫn thời gian đa thức )()2()1( ,...,, mCCC  ?),()),( )1()( 1 1 )1()( BCCdCCd m m i ii      3- 9 1(Hamiltonian)2(TSP) với B = n 2 1 2.2. Bài toán NP_Comlete (NPC)  Định Nghĩa: Chúng ta nói L là bài toán thuộc NPC nếu khẳng định sau là đúng 1) L  NP 2)  L’ NP, có phép dẫn với thời gian đa thức từ L’ về L * Bài toán SAT  Bài toán SAT được phát biểu dưới dạng bt quyết định: Instance: Cho trước n biến logic {x1, x2, .. ,xn} và một tập hợp C tuyển của các tục biến (biến hoặc phủ định của biến). Question: Tồn tại hay không một phép gán giá trị cho các biến sao cho mỗi cC có giá trị đúng? Ví dụ C1 = {x1 v x2,, x1 v x2 v ¬x4, x5}. C2 = {¬ x1, ¬ x2, x1 v x2v ¬ x4, x4}.  Định lý: Bài toán SAT là NPC 2.3. Bài toán NPC 3.1 MỘT SỐ ĐỊNH LÝ: NP_Comlete (NPC) * Đ/L1: Ta có 1 2 thì - Nếu 1NPC, 2NP thì 2NPC - Nếu 2P thì 1P. 3.2. Bài toán NP_Comlete (NPC) * Đ/L2: - Nếu có một bài toán NPC giải được trong thời gian đa thức bởi máy TRTĐ thì P=NP. - Nếu một bt bài toán NP nào đó không giải được trong thời gian đa thức bởi máy TRTĐ thì tất cả các bài toán NPC đều không giải được trong thời gian đa thức bởi máy TRTĐ.  Chứng minh bài toán  NPC: chúng ta thực hiện 4 bước sau: 1) Chứng minh bt  NP. 2) Lựa chọn bt ’ NPC. 3) Xây dựng hàm biến đổi f từ ’ sang  4) Chứng minh rằng f là một biến đổi đa thức. 3.2. Một số bài toán NPC Sơ đồ chứng minh một số bài toán NPC 3.3. Một số bài toán NPC * Bài toán 3SAT  Bài toán 3SAT được phát biểu dưới dạng bt quyết định như sau: Instance: Cho trước n biến logic {x1, x2, .. ,xn} là tập hợp C các tuyển gồm 3 tục biến, Ví dụ: C = {x1 v x2v x3 , x1 v x2 v ¬x4}. Question: Tồn tại hay không một phép gán giá trị cho các biến sao cho mọi cC đều đúng?  Định lý: Bài toán 3SAT là NPC 3.3. Một số bài toán NPC  Bài toán VC (Vertex Cover) Instance: Cho đồ thị G=(V,E) và một số nguyên dương k≤|V| Question: Tồn tại hay không một tập phủ đỉnh có kích cỡ ≤ k? 3.3 Một số bài toán NPC  Bài toán Clique Instance: Cho đồ thị G=(V,E) và một số nguyên dương k≤|V| Question: Tồn tại hay không trong G một đồ thị con đầy đủ với ít nhất k đỉnh? 3.3 Một số bài toán NPC  Bài toán 3DM (3-dimensional Matching) Instance: |W|=|X|=|Y|=q, Question: Tồn tại M tập con q phần tử của W×X×Y sao cho không có 2 phần tử nào của M có tọa độ chung? 3.3 Một số bài toán NPC  Bài toán Phân hoạch (Partition) Instance: A = {a1 , a2, , an } Question: Tồn tại hay không phân hoạch A = A A sao cho 3.3 Một số bài toán NPC ?a 21 A i  A ia 3.4 Bài toán NPH (NP-hard) Định Nghĩa: L là bài toán thuộc NPH nếu L’  NP có phép dẫn với thời gian đa thức từ L’ về L.