Bài toán quyết định (Decision Problem - DP) là bài toán chỉ có câu trả lời là có hoặc không (hay còn gọi là trả lời nhị phân). Mỗi thể hiện của bài toán nghĩa là mỗi trường hợp cá biệt của bài toán có một trả lời. Một bài toán quyết định Π đơn giản bao gồm một tập hợp DΠ các thể hiện và tập con YΠ Í DΠ là các thể hiện bài toán quyết định phát biểu dưới dạng: Instance: Question: . | The theory of NP-Completeness CHUYÊN ĐỀ: LÝ THUYẾT ĐỘ PHỨC TẠP THUẬT TOÁN LÝ THUYẾT NP - ĐẦY ĐỦ (THE THEORY OF NP - COMPLETENESS) Giáo viên : Thầy Vũ Đình Hoà The theory of NP-Completeness NỘI DUNG Bài toán quyết định Ngôn ngữ và lược đồ mã hóa Máy Turing tất định và lớp P Tính toán không tất định và lớp NP Mối quan hệ giữa lớp P và lớp NP Phép dẫn thời gian đa thức và lớp NPC Thuyết Cook The theory of NP-Completeness 1. BÀI TOÁN QUYẾT ĐỊNH Bài toán quyết định (Decision Problem - DP) là bài toán chỉ có câu trả lời là có hoặc không (hay còn gọi là trả lời nhị phân). Mỗi thể hiện của bài toán nghĩa là mỗi trường hợp cá biệt của bài toán có một trả lời. Một bài toán quyết định ∏ đơn giản bao gồm một tập hợp D∏ các thể hiện và tập con Y∏ D∏ là các thể hiện đúng The theory of NP-Completeness 1. BÀI TOÁN QUYẾT ĐỊNH Một bài toán quyết định phát biểu dưới dạng: Instance: Question: Ví dụ 1: bài toán sự đẳng cấu của đồ thị con Instance: Cho 2 đồ thị G1 = (V1, E1) và G2 = (V2, E2) Question: đồ thị G1 có chứa một đồ thị con G1’ mà G1’ đẳng cấu với đồ thị G2 hay không? The theory of NP-Completeness Giải thích về đồ thị đẳng cấu: G1’ đẳng cấu với G2 nếu như có |V1’| = |V2|, |E1’| = |E2| và ở đó tồn tại một song ánh f : V2 V1’ sao cho {u,v} E2 khi và chỉ khi {f(u), f(v)} E1’). 1. BÀI TOÁN QUYẾT ĐỊNH The theory of NP-Completeness 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. BÀI TOÁN QUYẾT ĐỊNH The theory of NP-Completeness Một bài toán quyết định có thể được chuyển hoá từ một bài toán tối ưu. Ví dụ: Bài toán tối ưu là “tìm một đường đi có độ dài nhỏ nhất trong số tất cả các đường đi nối 2 đỉnh đồ thị” ↔ BTQĐ : thêm vào một tham số B và hỏi xem có đường đi nào có . | The theory of NP-Completeness CHUYÊN ĐỀ: LÝ THUYẾT ĐỘ PHỨC TẠP THUẬT TOÁN LÝ THUYẾT NP - ĐẦY ĐỦ (THE THEORY OF NP - COMPLETENESS) Giáo viên : Thầy Vũ Đình Hoà The theory of NP-Completeness NỘI DUNG Bài toán quyết định Ngôn ngữ và lược đồ mã hóa Máy Turing tất định và lớp P Tính toán không tất định và lớp NP Mối quan hệ giữa lớp P và lớp NP Phép dẫn thời gian đa thức và lớp NPC Thuyết Cook The theory of NP-Completeness 1. BÀI TOÁN QUYẾT ĐỊNH Bài toán quyết định (Decision Problem - DP) là bài toán chỉ có câu trả lời là có hoặc không (hay còn gọi là trả lời nhị phân). Mỗi thể hiện của bài toán nghĩa là mỗi trường hợp cá biệt của bài toán có một trả lời. Một bài toán quyết định ∏ đơn giản bao gồm một tập hợp D∏ các thể hiện và tập con Y∏ D∏ là các thể hiện đúng The theory of NP-Completeness 1. BÀI TOÁN QUYẾT ĐỊNH Một bài toán quyết định phát biểu dưới dạng: Instance: Question: Ví dụ 1: bài toán sự đẳng cấu của đồ thị con Instance: Cho 2 đồ thị G1 = (V1, .
