Bài giảng NP - Complete

NP - Complete 2013-11-25 2 Một số bài toán tối ưu rời rạc Bài toán người du lịch: Cho n điểm trên mặt phẳng (thành phố), giữa hai thành phố bất kỳ được xác định một thông số là chi phí đi lại. Một hành trình là một cách đi xuất phát từ một thành phố nào đó, qua n thành phố và quay về nơi xuất phát. OP (Optimization Problem): Tìm hành trình * có tổng chi phí bé nhất. DP (Decision Problem): Có tồn tại một hành trình với chi phí D? 2013-11-25 3 Một số bài toán tối ưu rời rạc Bài toán tô màu đồ thị: Cho đồ thị G ={V,E}. OP: Số màu ít nhất để tô đồ thị G? DP: Cho số nguyên K. Có tồn tại hay không cách tô màu đồ thị G với số màu không quá K? Một cách tô màu đồ thị là một phương án gán cho mỗi đỉnh một màu, sao cho hai đỉnh liền kề có hai màu khác nhau. 2013-11-25 4 Một số bài toán tối ưu rời rạc Bài toán cái túi: Cho n đồ vật với kích thước là các số nguyên s1, s2, ..., sn và các túi với kích thức là số nguyên T. OP: Tìm số túi ít nhất để xếp các đồ vật. DP: Cho số nguyên K. Có tồn tại cách xếp các đồ vật vào không quá K túi với sức chứa T? 2013-11-25 5 Một số bài toán tối ưu rời rạc Bài toán tập con: Cho số nguyên dương T và tập X gồm n số nguyên dương a1, a2, ..., an. OP: Xác định tập con của X sao cho tổng của chúng gần nhất và không quá T. DP: Có tồn tại tập con sao cho tổng kích thước đúng bằng T. 2013-11-25 6 Một số bài toán tối ưu rời rạc Bài toán phân công công việc: Giả thiết có n công việc:  Mỗi thời điểm chỉ thực hiện một công việc,  Thời gian thực hiện t1, t2, ..., tn,  Thời hạn hoàn thành d1, d2, ..., dn (tính từ khi bắt đầu công việc đầu tiên),  Mức phạt đối với mỗi công việc bị chậm là p1, p2, ..., pn. Phân công công việc là một hoán vị  của tập J={1, 2,..., n}: J(1), J(2), ..., J(n). Tổng giá trị phạt của phân công : OP: Tìm lịch sắp xếp công việc có giá trị hàm phạt thấp nhất P()  min. DP: Cho trước k, xác định lịch  có mức phạt không quá k: P()  k.     n j jjj pdttP 1 )()()()1( 0elsethen...if  2013-11-25 7 Lớp P Thuật toán có độ phức tạp O(f(n)) nếu với mọi bộ số liệu có độ dài n, số phép tính phải thực hiện không quá C*f(n), với C >0. Thuật toán có độ phức tạp O(p(n)), với p(n) là một đa thức, gọi là có độ phức tạp đa thức. Định nghĩa: P là lớp các bài toán được giải với thời gian đa thức. Chú ý:  Không phải mọi bài toán thuộc lớp P đã có thuật toán hiệu quả.  Nếu bài toán không thuộc lớp P thì đều phải trả giá rất đắt về thời gian hoặc thậm chí không giải được nó trong thực tế. 2013-11-25 8 Lớp NP (Nondeterministic Polynomial) NP là lớp các bài toán quyết định mà việc kiểm tra lời giải đối với dữ liệu vào được thực hiện với thời gian đa thức. 2013-11-25 9 Lớp NP (Nondeterministic Polynomial) Thuật toán bất định (nondeterministic algorithm): Pha bất định: Một xâu kí tự S bất kỳ được sinh ra trong bộ nhớ, có thể coi như lời giải đề nghị. Pha tiền định: Đọc dữ liệu vào (S có thể bị bỏ qua). Thuật toán có thể kết thúc với khẳng định “Yes”, “No”, hoặc rơi vào vòng lặp không dừng. Có thể coi là pha kiểm tra lời giải đề nghị S. NP là lớp bài toán giải được bằng thuật toán bất định với thời gian đa thức (nondeterministic polynomial bouded). Thuật toán bất định là đa thức nếu tồn tại đa thức p sao cho với mỗi dữ liệu vào có kích thước n và có trả lời “yes” với tính toán của thuật toán là đa thức. 2013-11-25 10 Lớp NP Ví dụ: đồ thị có 5 đinh, 8 cạnh và k =4: V ={1, 2, 3, 4, 5}, E={(1,2), (1,4), (2,4), (2,3), (3,5), (2,5), (3,4), (4,5)} Kí hiệu: R (Red), B (Blue), G (Green), O (Orange), Y (Yellow). 1 2 4 3 5 Dùng 4 màu, các cặp đỉnh kề khác màuYesRGRBY Dùng tới 5 màuNoRBYGO Đỉnh 5 không được tô màuNoRGRB Đỉnh 2 và 5 cùng màuNoRGRBG ReasonOutputS 2013-11-25 11 Lớp P vs. NP Hiển nhiên: P  NP NP \ P = ? (NP  P?) P Sắp xếp Cây khung bé nhất Nhân ma trận Tìm kiếm tuần tự Đường đi ngắn nhất ... NP Bài toán cái túi Bài toán ba lô Bài toán người du lịch 2013-11-25 12 NP-đầy đủ (NP-complete) Hiển nhiên: P  NP. Nhưng: NP \ P = ? Chứng minh được: Trong NP có những bài toán khó không kém bất cứ bài toán nào khác trong NP.  A NP: nếu có một thuật toán đa thức nào giải được A thì với mọi bài toán B NP đều có thuật toán đa thức để giải B. Bài toán A được gọi là NP-đầy đủ. Nói cách khác, A NP được gọi là NP- đầy đủ nếu A P thì suy ra P=NP. P Sắp xếp Cây khung bé nhất Nhân ma trận Tìm kiếm tuần tự Đường đi ngắn nhất ... NP Bài toán cái túi Bài toán ba lô Bài toán người du lịch 2013-11-25 13 NP-đầy đủ (NP-complete) Hiển nhiên: P  NP. Nhưng: NP \ P = ? Chứng minh được: 1. Nếu NP ≠ P thì có bài toán thuộc NP nhưng không thuộc P và cũng không phải NP-đầy đủ. 2. Nhiều bài toán là NP-đầy đủ. P Sắp xếp Cây khung bé nhất Nhân ma trận Tìm kiếm tuần tự Đường đi ngắn nhất ... NP- đầy đủ NP 2013-11-25 14 NP-đầy đủ (NP-complete) Như vậy, để chỉ ra một bài toán nào đó là NP-đầy đủ cần chỉ ra rằng: Tồn tại một thuật toán đa thức bất định để giải nó (tức là chỉ ra nó thuộc lớp NP); Có một bài toán NP-đầy đủ dẫn về nó. P Sắp xếp Cây khung bé nhất Nhân ma trận Tìm kiếm tuần tự Đường đi ngắn nhất ... NP- đầy đủ NP 2013-11-25 15 NP-đầy đủ (NP-complete) Giả thiết cần giải bài toán A và có thuật toán giải bài toán B. Giả sử có ánh xạ T chuyển mỗi dữ liệu vào x của bài toán A thành dữ liệu vào T(x) của bài toán B T: x T(x) sao cho: Lời giải y của bài toán A với dữ liệu vào x tương ứng với Lời giải z của bài toán B với dữ liệu vào T(x) (nếu y là ”yes” thì z cũng là ”yes”). Thuật toán giải bài toán A = {Ánh xạ T + Thuật toán giải B} 2013-11-25 16 Bài toán CNF-SAT Mô tả: 1) Biến logic nhận một trong hai giá trị: true hoặc false. Kí hiệu a là biến logic, là phủ định của a. Nếu a nhận giá trị true thì nhận giá trị false và ngược lại, nếu a nhạn giá trị false thì nhận giá trị true. Một tên biến là một biến logic hoặc phủ định của biến logic (cũng là một biến logic). 2) Một mệnh đề là một dãy các tên biến được xen kẽ bới phép toán logic OR (). 3) Một biểu thức logic trong dạng liên kết chuẩn (conjunction nomal form - CNF) là một dãy các mệnh đề được kết nối bới phép toán AND (). Bài toán quyết định: Khi các biến nhận giá trị true hoặc false, biểu thức có nhận giá trị true hay không? 2013-11-25 17 Bài toán CNF-SAT Định lý Cook: Bài toán CNF-SAT là NP-đầy đủ Cần chỉ ra rằng bất kỳ bài toán NP nào (A) cũng dẫn chuyển về CNF-SAT: Cần xây dựng ánh xạ T dẫn chuyển input x của bài toán A về một biểu thức logic. Lời giải của bài toán quyết định A trùng với giá trị true hoặc false của CNF-SAT. 2013-11-25 18 Bài toán CNF-SAT Định lý Cook: Bài toán CNF-SAT là NP-đầy đủ x dữ liệu vào của A “yes” hoặc “no” T(x) T CNF-SAT Algorithm for A 2013-11-25 19 Bài toán CNF-SAT Ví dụ: Xét bài toán 3-CG: Đồ thị G ={V,E} như hình vẽ có tô được bằng 3 màu? a db c Chuyển dẫn bài toán 3-CG về bài toán CNF-SAT? 2013-11-25 20 Bài toán CNF-SAT u1 u4u3 u2 Ký hiệu: xkj – đỉnh k tô bởi màu j Xét 32 mệnh đề: C(k) = {xk1, xk2, xk3}, đỉnh k được tô bởi ít nhất 1 màu A(k) = {xk1, xk2,}, đỉnh k không cùng được tô màu 1 và 2 B(k) = {xk2, xk3}, đỉnh k không cùng được tô màu 2 và 3 C(k) = {xk1, xk3}, đỉnh k không cùng được tô màu 1 và 3 k = a, b, c, d M = C(a) & ..&C(d)&A(a)&..&A(d)&B(a)&..&B(d)&C(a)&..&C(d) M = true nếu mỗi đỉnh được tô bởi đúng 1 trong ba màu {1, 2, 3} 2013-11-25 21 Bài toán CNF-SAT u1 u4u3 u2 Ký hiệu: e=(u,v) E, u,v V D(e,j) ={ xuj, xvj } - đỉnh u và v không cùng tô bởi màu j N = D((u1,u2),1)&D((u1,u3),1)&D((u1,u4),1)& D((u2,u3),1)&D((u2,u4),1)&D((u3,u4),1) &...& D((u1,u2),3)&D((u1,u3),3)&D((u1,u4),3)& D((u2,u3),3)&D((u2,u4),3)&D((u3,u4),3) N = true nếu hai đỉnh không được tô bởi cùng 1 trong ba màu {1, 2, 3} G là đồ thị 3 màu chỉ khi M&N có giá trị true. 2013-11-25 22 NP-đầy đủ Ví dụ 2: Bài toán tổng tập con chuyển dẫn được về bài toán lập lịch Cho số nguyên dương T và tập n số nguyên dương X={ a1, a2, ..., an} Tìm tập con của X sao cho tổng của chúng gần nhất với T. n công việc: J1, J2, ..., Jn; thời gian thực hiện: t1, t2, ..., tn; thời hạn hoàn thành (từ khi bắt đầu dự án): d1, d2, ..., dn mức phạt chậm quá thời hạn: p1, p2, ..., pn. Mỗi thời điểm chỉ thực hiện một công việc. Phân công công việc : {1, 2,..., n}  {(1), (2),..., (n)} Thứ tự thực hiện: J(1), J(2),...,J(n). Tổng giá trị phạt của phân công trên là     n j jjj pdttP 1 )()()()1( 0elsethen...if  2013-11-25 23 NP-đầy đủ Ví dụ 2: Bài toán tổng tập con chuyển dẫn được về bài toán lập lịch Nếu i=1,..,nsi < T bài toán tập con không có lời giải. Có thể chuyển dẫn phương án thành bất kỳ dữ liệu vào cho bài toán phân công công việc mà không có lời giải. Ví dụ: ti= 2, di = pi = 1, với i = 1, 2, ..., n. and k=0. (Bài toán quyết định: Có tồn tại một tập con sao cho tổng đúng bằng T? Có tồn tại một lịch công tác  mà tổng giá trị phạt P  k ?.) 2013-11-25 24 NP-đầy đủ Ví dụ 2: Bài toán tổng tập con chuyển dẫn được về bài toán lập lịch Xét trường hợp i=1,..,nsi  T Đặt ti = si, di = T, pi = si, với i = 1, ..., n và k = i=1,..,nsi  T. Giả sử J  NS = {1, 2,...,n} iJsi = T Đặt:  : J  { 1, 2, ..., |J|},  : NS\J  { |J|+1,...,n}, Ttss J i i J i i Ji i   || 1 )( || 1 )(  ||...,,2,1, 1 )( JjTt j i i    Các công việc từ |J|+1 cho đến n đều quá hạn, giá trị phạt: kTssssp n i i Ji i n i i n Ji i n Ji i    111|| )( 1|| )(  2013-11-25 25 NP-đầy đủ Ví dụ 2: Bài toán tổng tập con chuyển dẫn được về bài toán lập lịch Ngược lại: giả sử  là một phân công công việc với mức phạt không quá k. Kí hiệu m là số nguyên lớn nhất thoả mãn: Tt m i i  1 )( Tskp n mi n i ii    1 1 )(Giá trị phạt: TssTss n mi i m i i n i i n mi i   1 )( 1 )( 11 )(    m i isT 1 )( Ts m i i  1 )( Vậy s(1), s(2), ..., s(m) là lời giải bài toán tổng tập con. 2013-11-25 26 NP-đầy đủ Sơ đồ chứng minh A là bài toán NP-đầy đủ: Chỉ ra rằng A thuộc lớp NP; Chọn bài toán NP-đầy đủ nào đó, ví dụ là B và chuyển dẫn B về A Thật vậy: A là NP-đầy đủ nếu A thuộc lớp NP và mọi bài toán X thuộc lớp NP có XA. B là NP-đầy đủ nên mọi bài toán C trong NP: CB Do BA, suy ra CA. Nghĩa là mọi bài toán C trong NP đều chuyển dẫn về A được. 2013-11-25 27 NP-đầy đủ 1) Thông thường, việc chỉ ra rằng một bài toán A nào đó thuộc lớp NP là khó (phải chỉ ra được thuật toán bất định giải nó trong thời gian đa thức). 2) Việc tìm được bài toán NP-đầy đủ để chuyển dẫn về A xem ra có thể đơn giản hơn. Việc chuyển dẫn được chứng tỏ nó có độ khó tương đương với bài toán NP-đầy đủ. Những bài toán như vậy gọi là NP-khó. 2013-11-25 28 Remark Bài toán tìm đường đường đi ngắn nhất nối hai đỉnh của đồ thị liên thông có trọng số có thuật toán hiệu quả để giải. Tuy nhiên, bài toán tìm đường đi dài nhất nối hai đỉnh là bài toán NP-đầy đủ. Bài toán xác định đồ thị G-2 màu khá đơn giản. Tuy nhiên, bài toán kiểm tra G-3 màu lại là NP-đầy đủ. Cho đồ thị có hướng G={V,E}, số nguyên k, tập con E’ E thoả mãn |E’|k. E’ có chứa cạnh của các chu trình trong G? Bài toán này được chứng mình là NP-đầy đủ, tuy nhiên nếu xét bài toán này với đồ thị vô hướng, nó lại thuộc lớp P.