DAA - Lớp P & NP
Trong Khoa học Máy tính, nhiều vấn đề được giải quyết trong đó mục tiêu là tối đa hóa hoặc giảm thiểu một số giá trị, trong khi trong các vấn đề khác, chúng tôi cố gắng tìm xem có giải pháp hay không. Do đó, các vấn đề có thể được phân loại như sau:
Vấn đề tối ưu hóa
Các vấn đề về tối ưu hóa là những vấn đề mà mục tiêu là tối đa hóa hoặc giảm thiểu một số giá trị. Ví dụ,
Tìm số màu tối thiểu cần thiết để tô màu một đồ thị đã cho.
Tìm đường đi ngắn nhất giữa hai đỉnh trong đồ thị.
Vấn đề quyết định
Có nhiều vấn đề mà câu trả lời là Có hoặc Không. Những loại vấn đề này được gọi là decision problems. Ví dụ,
Cho dù một biểu đồ nhất định chỉ có thể được tô màu bởi 4 màu.
Tìm chu trình Hamilton trong đồ thị không phải là vấn đề quyết định, trong khi kiểm tra đồ thị có phải là Hamilton hay không là vấn đề quyết định.
Ngôn ngữ là gì?
Mọi vấn đề quyết định chỉ có thể có hai câu trả lời, có hoặc không. Do đó, một vấn đề quyết định có thể thuộc về một ngôn ngữ nếu nó cung cấp câu trả lời 'có' cho một đầu vào cụ thể. Một ngôn ngữ là tổng số các đầu vào mà câu trả lời là Có. Hầu hết các thuật toán được thảo luận trong các chương trước làpolynomial time algorithms.
Đối với kích thước đầu vào n, nếu độ phức tạp thời gian trong trường hợp xấu nhất của một thuật toán là O(nk), Ở đâu k là một hằng số, thuật toán là một thuật toán thời gian đa thức.
Các thuật toán như Phép nhân chuỗi ma trận, Đường dẫn ngắn nhất nguồn đơn, Đường dẫn ngắn nhất theo cặp, Cây kéo dài tối thiểu, v.v. chạy trong thời gian đa thức. Tuy nhiên, có rất nhiều vấn đề, chẳng hạn như nhân viên bán hàng đi du lịch, tô màu đồ thị tối ưu, chu trình Hamilton, tìm đường đi dài nhất trong đồ thị và thỏa mãn công thức Boolean mà không có thuật toán thời gian đa thức nào được biết đến. Những vấn đề này thuộc về một loại vấn đề thú vị, được gọi làNP-Complete vấn đề, mà trạng thái không xác định.
Trong bối cảnh này, chúng ta có thể phân loại các vấn đề như sau:
P-Class
Lớp P bao gồm những bài toán có thể giải được trong thời gian đa thức, tức là những bài toán này có thể được giải quyết kịp thời O(nk) trong trường hợp xấu nhất, ở đâu k là hằng số.
Những vấn đề này được gọi là tractable, trong khi những người khác được gọi là intractable or superpolynomial.
Về mặt hình thức, một thuật toán là thuật toán thời gian đa thức, nếu tồn tại một đa thức p(n) sao cho thuật toán có thể giải quyết bất kỳ trường hợp nào có kích thước n trong một thời gian O(p(n)).
Vấn đề yêu cầu Ω(n50) thời gian để giải quyết về cơ bản là khó khăn đối với n. Thuật toán thời gian đa thức được biết đến nhiều nhất chạy trong thời gianO(nk) cho giá trị khá thấp của k.
Ưu điểm trong việc xem xét lớp các thuật toán đa thức thời gian là tất cả đều hợp lý deterministic single processor model of computation có thể được mô phỏng trên nhau với nhiều nhất là đa thức slow-d
NP-Class
Lớp NP bao gồm những vấn đề có thể kiểm chứng được trong thời gian đa thức. NP là loại các vấn đề quyết định mà bạn có thể dễ dàng kiểm tra tính đúng đắn của một câu trả lời đã xác nhận, với sự trợ giúp của một ít thông tin bổ sung. Do đó, chúng tôi không yêu cầu một cách để tìm ra giải pháp, mà chỉ để xác minh rằng một giải pháp bị cáo buộc thực sự là đúng.
Mọi vấn đề trong lớp này có thể được giải quyết trong thời gian theo cấp số nhân bằng cách sử dụng tìm kiếm toàn diện.
P so với NP
Mọi vấn đề quyết định có thể giải được bằng thuật toán thời gian đa thức xác định cũng có thể giải được bằng thuật toán thời gian không xác định đa thức.
Tất cả các vấn đề trong P có thể được giải quyết bằng các thuật toán thời gian đa thức, trong khi tất cả các vấn đề trong NP-P là không thể chữa được.
Không biết liệu P = NP. Tuy nhiên, nhiều bài toán đã biết trong NP với tính chất là nếu chúng thuộc P thì có thể chứng minh rằng P = NP.
Nếu P ≠ NP, có những vấn đề trong NP mà không phải trong P cũng không phải trong NP-Complete.
Vấn đề thuộc về lớp Pnếu dễ dàng tìm ra giải pháp cho vấn đề. Vấn đề thuộc vềNP, nếu dễ dàng kiểm tra một giải pháp có thể rất tẻ nhạt để tìm.