Co-NP

Овај проблем представља један од неразјашњених проблема у рачунарским наукама. У теорији рачунске комплексности, co-NP представља класу комплексности. Проблем одлуке Χ је члан co-NP ако и само ако је његов комплемент у класи комплексности NP. Једноставније речено, co-NP је класа проблема за коју постоји ефикасни верификовани доказ "no" инстанце, некад поменут и као контрапример. Самим тим, можемо рећи и да је co-NP скуп проблема одлуке где се "no" инстанце могу прихватити у полиномијалном времену од стране недетерминистичке Тјурингове машине.

Пример NP комплетног проблема је проблем суме подскупа: ако нам је дат коначан скуп целих бројева, да ли постоји непразан подскуп чија је сума нула? Да би се дао доказ да је ово тачно, мора се специфицирати непразни подскуп у ком је сума чланова нула. Комплементарни проблем је у домену co-NP и поставља питање: "Ако нам је дат коначан скуп целих бројева, да ли се сваки непразни подскуп тог скупа састоји од чланова који дају збир различит од нуле?"

Однос са другим класама

P, класа проблема решивих у полиномијалном времену, је подскуп од NP и co-NP проблема. P се сматра да је стриктни подскуп у оба случаја (и самим тим не може бити стриктан у једном случају а у другом да не буде). За NP и co-NP се сматра да су неједнаки. Ако је то тачно, онда ниједан NP-комплетан проблем не може бити у co-NP скупу проблема и ниједан co-NP-комплетан проблем не може бити у NP скупу проблема.

Ово се може доказати на следећи начин: претпоставимо да постоји NP-комплетан проблем Χ који се налази у скупу co-NP проблема. С обзиром на чињеницу да се сви проблеми у NP скупу могу редуковати на Χ, из тога следи да за сваки проблем у NP можемо конструисати недетерминистичку Тјурингову машину која ће пронаћи његов комплемент у полиномијалном времену, на пример NP ⊆ co-NP. Из овога следи да је скуп комплемената проблема у NP подскуп комплемената проблема у co-NP, i.e., co-NP ⊆ NP. Из тога следи co-NP = NP. Доказ да ниједан co-NP-комплетан проблем не може бити у NP ако је NP ≠ co-NP је симетричан.

Ако је доказано да је проблем и у NP и co-NP скуповима, онда је то генерално прихваћено као доказ да проблем вероватно није NP-комплетан (јер би у том случају било NP = co-NP).

Факторизација целих бројева је уско повезана са проблемом простих бројева. Алгоритам факторизације целих бројева показује да ли је број прост или није. Ово не важи за супротни случај: за тест простих бројева довољно је показати да постоји фактор када се проверава сложеност броја. И тест простих бројева и факторизација су дуго сматрани за NP и co-NP проблеме. АКС тест простих бројева, објављен 2002. године, показује да је тестирање да ли је број прост такође у скупу P. За саму факторизацију није сигурно да ли има алгоритам у полиномијалном времену.

Види још

• Неразјашњени проблеми у рачунарским наукама
• П = НП проблем
• Полиномијално време
• Теорија комплексности
• НП-комплетни проблеми

Литература

• 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. стр. 155.
• Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), no. 2. стр. 781-793.