Chương 3: Chứng minh các kết quả của bài toán NP_đầy đủ

Chia sẻ: Nguyễn Gia Thế | Ngày: | Loại File: PPT | Số trang:25

Thêm vào BST

Báo xấu

142
lượt xem 15
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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). 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

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chương 3: Chứng minh các kết quả của bài toán NP_đầy đủ

Chứng minh các kết quả Chương 3: 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 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
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) 2.1. Phép dẫn với thời gian đa thức Cho hai bài toán ∏ 1 và ∏ 2. Ta biết rằng π 1 = π Y1 ∪ π N1 π 2 = π Y2 ∪ π N 2
2.1. Phép dẫn với thời gian đa thức Một phép biến đổi f mỗi dữ kiện ∏ 1 thành dữ kiện ∏ 2 và thỏa mãn 2 điều kiện sau được gọi là phép dẫn thời gian đa thức : 1. f được thực hiện trong thời gian đa thức f (π Y1 ) ⊆ π Y2 2. f (π N1 ) ⊆ π N 2 Định Nghĩa: Một bt quyết định ∏ 1 dẫn về bt quyết định ∏ 2 trong thời gian đa thức nếu tồn tại một phép dẫn đa thức từ bt ∏ 1 về bt ∏ 2. Ký hiệu: ∏ 1 ∝ ∏ 2
1. Ví dụ phép dẫn thời gian đa thức Ví dụ 1: Chu trình Hamilton Instance: Đồ thị G vô hướng. Question: tồn tại hay không một chu trình đi qua tất cả đỉnh của đồ thị ? The theory of NP-Completeness 7
1. BÀI TOÁN QUYẾT ĐỊNH Ví dụ 2: Traveling Salesman Instance: Tập hữu hạn các thành phố: C = {c1, c2,…cm}, khoảng cách giữa hai thành phố ci, cj là d(ci, cj) ∈ Z+, một số B ∈ Z+. Question: tồn tại hay không một đường đi nào qua tất cả các thành phố trong C mà có tổng độ dài không lớn hơn B? (Tồn tại một sắp thứ tự sao cho π (1) , Cπ ( 2) ,..., Cπ ( m ) C m −1 (∑ d (C π (i ) , C π (i +1) )) + d (C π ( m ) , C π (1) ) ≤ B ) i =1 The theory of NP-Completeness 8
1. Phép dẫn thời gian đa thức Phép dẫn f biến mỗi đồ thị G thành một đồ thị đầy đủ có trọng số bằng cách thêm các cạnh mới nối các cặp đỉnh của G và gán trọng số các cạnh cũ là 1, các cạnh mới thêm vào là 2 và chọn B = n là số đỉnh của đồ thị G. The theory of NP-Completeness 9
Proof of Hamiltonian ∝ TSP 1 2 3- 10
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
2.2 Bài toán NP_Comlete (NPC)  Sau đây là các định lý NPC, nó cũng là điểm then chốt của việc quyết định P thực tế có bằng NP hay không? * Đ/L1: Ta có một phép dẫn với thời gian đa thức từ bt ∏ 1 về bt ∏ 2 , ( ký hiệu ∏ 1 ∝ ∏ 2 ) - Nếu bt ∏ 1∈NPC, bt ∏ 2∈NP => ∏ 2∈NPC - Nếu bt ∏ 2∈P => bt ∏ 1∈P
2.2. Bài toán NP_Comlete (NPC) * Đ/L2: - Nếu có một bài toán NPC bất kỳ giải được trong thời gian đa thức thì P=NP. - Ngược lại, nếu một bt bài toán NP bất kỳ không giải được trong thời gian đa thức thì tất cả các bài toán NPC đều không giải được trong thời gian đa thức
3.3. Một số bài toán NPC Bằng việc sử dụng kỹ thuật dẫn bt1 về bt2 (đã có thuật toán giải quyết) với 1 phép dẫn thích hợp giúp chúng ta có thể biến mỗi dữ kiện của bt1 thành dữ kiện tương ứng của bt2, nhờ đó mà có thể chuyển thuật toán giải quyết bt2 thành thuật toán tương đương để giải quyết bt1. Trong một bài báo của Stephen Cook, giới thiệu năm 1971 đã nêu nên một số vấn đề quan trọng như những nền tảng cho việc nghiên cứu về các bài toán NPC, đó là:
3.3. Một số bài toán NPC  Một là, S.Cook đã nhấn mạnh sự cần thiết của “phép dãn với thời gian đa thức”, đó là những bt mà đối với nó sự chuyển dẫn về yêu cầu có thể được xử lý bởi một thuật toán thời gian đa thức. Nếu chúng ta có một phép dãn với thời gian đa thức từ bt1 sang bt2, thì với bất kỳ một thuật toán thời gian đa thức nào cho bt2 đều có thể chuyển thành thuật toán thời gian đa thức tương đương cho bt1.  Hai là, S.Cook tập chung sự chú ý vào lớp NP của những bt quyết định mà có thể giải quyết với thời gian đa thức bằng một máy Turing không tất định, bởi vì hầu hết những bài toán khó khăn trong thực tiễn khi được phát biểu dưới dạng bt quyết định thì đều thuộc vào lớp NP.
3.3. Một số bài toán NPC  Ba là, S.Cook ông đã chứng minh được rằng một bt cụ thể trong NP đó là bt tính thoả được “satisfiability-SAT” có tính chất quan trọng là mọi bt thuộc lớp NP đều có thể dẫn về bt SAT trong thời gian đa thức. Tức là nếu bt SAT có thể được giải quyết bằng một thuật toán thời gian đa thức thì mọi bt trong NP cũng có thể được giải quyết như vậy. Như vậy bt SAT là vấn đề khó nhất (hardest) trong NP  Cuối cùng, S.Cook cho rằng, đó là sự tồn tại các bt khác trong NP có thể với bt SAT cũng là bt khó giải nhất. Ông ta minh chứng điều này bằng trường hợp đối với bt “liệu có một đồ thị G có chứa một đồ thị con hoàn chỉnh với k đỉnh không ?”.
3.3. Một số bài toán NPC  Sau khi đã biết SAT là bt NPC chúng ta sẽ trình bày một khuôn mẫu cho một quá trình dẫn một bt NPC thành chứng minh bài toán khác cũng là 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  Đây là con đường mới để chứng minh một số bt là NPC, chẳng hạn như bt người du lịch hay chu trình Hamilton. Về nguyên tắc chúng ta thực hiện điều đó bằng cách tìm các phép dẫn với thời gian đa thức từ bt SAT về mỗi bài toán cần chứng minh.  Tuy nhiên một bt trung gian quan trọng có tên 3SAT là dạng rút gọn của bt SAT, bt 3SAT dễ dẫn về các bt cần chứng minh hơn nhiều so với bt SAT
3.3. Một số 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 như sau: Instance: Cho trước n biến logic {x1, x2, x } là tập …….. , n hợp C các bộ biến hoặc phủ định của biến, gọi là tục biến, ví dụ C = {x1 v x2, x1 v x2 v ¬x4, x5}. 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? C = {¬ x1, ¬ x2, x1 v x2v ¬ x4, x4}.  Định lý: Bài toán SAT là 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, x } là tập …….. , n 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 có ít nhất một gia trị đúng?  Định lý: Bài toán 3SAT là NPC