Bài giảng Lý thuyết độ phức tạp: Chương 3 - PGS. TSKH Vũ Đình Hòa

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 đủ" cung cấp cho người đọc các kiến thức: Các khái niệm, các bài toán NP - Complete. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết độ phức tạp: Chương 3 - PGS. TSKH Vũ Đình HòaChươ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 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) 1.2. Lớp bài toán NP(Nondeterministic polynomial time) 1.3. Quan hệ giữa lớp P và lớp NPII. 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 NPCI. Các khái niệm1.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 định1.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. 1   Y   N 1 1  2  Y   N 2 22.1 Phép dẫn với thời gian đa thứcPhép dẫn thời gian đa thức f biến đổi mỗi dữ kiện 1thành dữ kiện 2 thỏa mãn : 1. f được thực hiện trong thời gian đa thức 2. f ( Y )   Y 1 2 f ( N1 )   N 2 Ký hiệu: 1  2Ví dụ phép dẫn thời gian đa thức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? The theory of NP-Completeness 7Ví dụ phép dẫn thời gian đa thức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 C (1) , C ( 2) ,..., C ( m) thỏa : m 1  d (C i 1 (i ) , C (i 1) ))  d (C ( m ) , C (1) )  B ? The theory of NP-Completeness 81(Hamiltonian)2(TSP) với B =n 1 2 3- 92.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 2.3. Bài toán NPC* 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à NPC3.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Đ.3.2. Một số bài toán NPC 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.3. 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, Questio ...