Co-NP

Vấn đề mở trong khoa học máy tính: Có phải NP = co-NP ? (các vấn đề mở khác trong khoa học máy tính)

Trong lý thuyết độ phức tạp tính toán, co-NP là một lớp độ phức tạp. Một ngôn ngữ ${\displaystyle {\mathcal {X}}}$ nằm trong co-NP khi và chỉ khi phần bù ${\displaystyle {\overline {\mathcal {X}}}}$ của nó nằm trong NP. Nói một cách đơn giản, co-NP là lớp các bài toán mà các trường hợp không có thể được kiểm chứng nhanh chóng, hay nói cách khác là tồn tại phản ví dụ dễ kiểm tra.

Một ví dụ của bài toán NP-đầy đủ là bài toán tổng tập hợp con: cho một tập hợp các số nguyên, tồn tại hay không một tập hợp con có tổng bằng không? Để chứng minh cho trường hợp "có", ta cần phải đưa ra một tập hợp con có tổng bằng không. Bài toán phản của bài toán đó nằm trong co-NP là như sau: "cho một tập hợp các số nguyên, có phải tất cả các tập hợp con đều có tổng khác không?" Để chứng minh cho trường hợp "không", ta phải đưa ra một tập hợp con có tổng bằng không, và việc kiểm tra là rất dễ dàng.

P, lớp các bài toán giải được trong thời gian đa thức, là tập hợp con của NP và co-NP. Người ta giả thuyết rằng P là tập con thực sự của cả hai (có thể chứng minh rằng nó không thể là tập con thực sự của một tập nhưng không phải tập con thực sự của tập kia). Người ta cũng giả thuyết rằng NP và co-NP là khác nhau^[1]. Nếu giả thuyết đó là đúng, thì mọi bài toán NP-đầy đủ không nằm trong co-NP và mọi bài toán co-NP-đầy đủ không nằm trong NP, và đồng thời P cũng khác NP do P là đóng với phép lấy phần bù.

Hệ quả thứ nhất ở trên của giả thuyết NP khác co-NP có thể chứng minh như sau. Giả sử tồn tại một bài toán NP-đầy đủ L trong co-NP. Do mọi bài toán trong NP có thể quy về L, với mỗi bài toán trong NP, tồn tại một máy Turing không đơn định giải quyết được phần bù của nó, nghĩa là, NP là tập hợp con của co-NP. Do đó tập hợp các phần bù của các bài toán trong NP là tập hợp con của tập hợp các phần bù của các bài toán trong co-NP, nghĩa là, co-NP là tập hợp con của NP. Như vậy, NP và co-NP bằng nhau. Chứng minh cho mọi bài toán co-NP-đầy đủ không nằm trong NP là tương tự.

Nếu một bài toán nằm trong cả NP và co-NP, đó thường được coi là một bằng chứng tốt nó không là NP-đầy đủ (vì nếu không thì NP = co-NP).

Một ví dụ của bài toán nằm trong cả NP và co-NP là phân tích ra thừa số nguyên tố: cho hai số nguyên dương m và n, quyết định xem m có thừa số lớn hơn 1 và nhỏ hơn n hay không. Việc bài toán nằm trong NP là hiển nhiên: nếu m có thừa số như vậy thì chính thừa số đó là một bằng chứng tốt. Việc bài toán đó nằm trong co-NP cũng đơn giản: bằng chứng chính là danh sách tất cả các thừa số nguyên tố của m, sau đó để kiểm tra, chỉ cần nhân các thừa số với nhau xem có thu được m và kiểm tra tính nguyên tố của các thừa số bằng thuật toán kiểm tra tính nguyên tố AKS.

Phân tích ra thừa số nguyên tố hay bị nhầm lẫn với bài toán kiểm tra tính nguyên tố. Cả hai bài toán đều nằm trong cả NP và co-NP. Thuật toán kiểm tra tính nguyên tố AKS, xuất bản năm 2002, chứng minh rằng bài toán kiểm tra tính nguyên tố nằm trong P, trong khi vẫn chưa biết có hay không thuật toán thời gian đa thức cho phân tích ra thừa số nguyên tố.^[2]

Tham khảo

1. Hopcroft, John E. (2000). Introduction to Automata Theory, Languages, and Computation (ấn bản thứ 2). Boston: Addison-Wesley. ISBN 0201441241. Chương 11.
2. Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004), “PRIMES is in P” (PDF), Annals of Mathematics, 160 (2): 781–793

Liên kết ngoài

• Bản mẫu:CZoo