Co-NP
Овај проблем представља један од неразјашњених проблема у рачунарским наукама. У теорији рачунске комплексности, co-NP представља класу комплексности. Проблем одлуке
Пример NP комплетног проблема је проблем суме подскупа: ако нам је дат коначан скуп целих бројева, да ли постоји непразан подскуп чија је сума нула? Да би се дао доказ да је ово тачно, мора се специфицирати непразни подскуп у ком је сума чланова нула. Комплементарни проблем је у домену co-NP и поставља питање: "Ако нам је дат коначан скуп целих бројева, да ли се сваки непразни подскуп тог скупа састоји од чланова који дају збир различит од нуле?"
Однос са другим класама
[уреди | уреди извор]P, класа проблема решивих у полиномијалном времену, је подскуп од NP и co-NP проблема. P се сматра да је стриктни подскуп у оба случаја (и самим тим не може бити стриктан у једном случају а у другом да не буде). За NP и co-NP се сматра да су неједнаки. Ако је то тачно, онда ниједан NP-комплетан проблем не може бити у co-NP скупу проблема и ниједан co-NP-комплетан проблем не може бити у NP скупу проблема.
Ово се може доказати на следећи начин: претпоставимо да постоји 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.