Xem mã nguồn của Co-NP

{{lowercase}}
{{vấn đề mở|khoa học máy tính|Có phải '''NP''' {{=}} '''co-NP''' ?}}
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ữ <math>{\mathcal{X}}</math> nằm trong co-NP khi và chỉ khi  [[phần bù (độ phức tạp)|phần bù]] <math>\overline{\mathcal{X}}</math> của nó nằm trong '''[[NP (độ phức tạp)|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<ref>
{{chú thích sách | first = John E. | last = Hopcroft | title = Introduction to Automata Theory, Languages, and Computation|edition=2| publisher = Addison-Wesley | location = Boston | year = 2000 | isbn = 0201441241 }} Chương 11.</ref>. 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 đủ {{mvar|L}} trong co-NP. Do mọi bài toán trong NP có thể quy về {{mvar|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 [[số nguyên tố|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ố.<ref>
{{chú thích|first1=Manindra|last1=Agrawal|first2=Neeraj|last2=Kayal|first3=Nitin|last3=Saxena|url=http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf|title=PRIMES is in P|journal=Annals of Mathematics|volume=160|year=2004|issue=2|pages=781&ndash;793}}</ref>

==Tham khảo==
{{Tham khảo}}

== Liên kết ngoài ==
* {{CZoo|coNP|C#conp}}

{{Lớp độ phức tạp}}

[[Thể loại:Lớp độ phức tạp]]