Co-NP

Ovaj problem predstavlja jedan od nerazjašnjenih problema u računarskim naukama. U teoriji računske kompleksnosti, co-NP predstavlja klasu kompleksnosti. Problem odluke Χ je član co-NP ako i samo ako je njegov komplement u klasi kompleksnosti NP. Jednostavnije rečeno, co-NP je klasa problema za koju postoji efikasni verifikovani dokaz "no" instance, nekad pomenut i kao kontraprimer. Samim tim, možemo reći i da je co-NP skup problema odluke gde se "no" instance mogu prihvatiti u polinomijalnom vremenu od strane nedeterminističke Tjuringove mašine.

Primer NP kompletnog problema je problem sume podskupa: ako nam je dat konačan skup celih brojeva, da li postoji neprazan podskup čija je suma nula? Da bi se dao dokaz da je ovo tačno, mora se specificirati neprazni podskup u kom je suma članova nula. Komplementarni problem je u domenu co-NP i postavlja pitanje: "Ako nam je dat konačan skup celih brojeva, da li se svaki neprazni podskup tog skupa sastoji od članova koji daju zbir različit od nule?"

Odnos sa drugim klasama

P, klasa problema rešivih u polinomijalnom vremenu, je podskup od NP i co-NP problema. P se smatra da je striktni podskup u oba slučaja (i samim tim ne može biti striktan u jednom slučaju a u drugom da ne bude). Za NP i co-NP se smatra da su nejednaki. Ako je to tačno, onda nijedan NP-kompletan problem ne može biti u co-NP skupu problema i nijedan co-NP-kompletan problem ne može biti u NP skupu problema.

Ovo se može dokazati na sledeći način: pretpostavimo da postoji NP-kompletan problem Χ koji se nalazi u skupu co-NP problema. S obzirom na činjenicu da se svi problemi u NP skupu mogu redukovati na Χ, iz toga sledi da za svaki problem u NP možemo konstruisati nedeterminističku Tjuringovu mašinu koja će pronaći njegov komplement u polinomijalnom vremenu, na primer NP ⊆ co-NP. Iz ovoga sledi da je skup komplemenata problema u NP podskup komplemenata problema u co-NP, i.e., co-NP ⊆ NP. Iz toga sledi co-NP = NP. Dokaz da nijedan co-NP-kompletan problem ne može biti u NP ako je NP ≠ co-NP je simetričan.

Ako je dokazano da je problem i u NP i co-NP skupovima, onda je to generalno prihvaćeno kao dokaz da problem verovatno nije NP-kompletan (jer bi u tom slučaju bilo NP = co-NP).

Faktorizacija celih brojeva je usko povezana sa problemom prostih brojeva. Algoritam faktorizacije celih brojeva pokazuje da li je broj prost ili nije. Ovo ne važi za suprotni slučaj: za test prostih brojeva dovoljno je pokazati da postoji faktor kada se proverava složenost broja. I test prostih brojeva i faktorizacija su dugo smatrani za NP i co-NP probleme. AKS test prostih brojeva, objavljen 2002. godine, pokazuje da je testiranje da li je broj prost takođe u skupu P. Za samu faktorizaciju nije sigurno da li ima algoritam u polinomijalnom vremenu.

Vidi još

• Nerazjašnjeni problemi u računarskim naukama
• P = NP problem
• Polinomijalno vreme
• Teorija kompleksnosti
• NP-kompletni problemi

Literatura

• Hopcroft, John E. (2000). Introduction to Automata Theory, Languages, and Computation (2nd Edition). Boston: Addison-Wesley. ISBN 978-0-201-44124-6. Chap. 11.
• Goldreich, Oded . P, NP, and NP-completeness: The Basics of Computational Complexity. Cambridge University Press. 2010. ISBN 978-1-139-49009-2. str. 155.
• Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), no. 2. str. 781-793.