Co-NP (Complexitat)
En complexitat computacional, co-NP és la classe de complexitat que conté els problemes de decisió complementaris de la classe NP. Per problema complementari s'entén aquell que te les respostes invertides. També es pot dir que els la classe co-NP és el conjunt de problemes de decisió que una màquina de Turing no determinista respon «no» (o rebutja) en un temps polinòmic.[1][2]
La classe de complexitat P és un subconjunt tant de NP com de co-NP i es pensa que la inclusió és estricta en tots dos casos. Es pensa també que NP i co-NP son diferents. Si això fos cert, cap problema NP-complet podria estar a co-NP i cap problema de co-NP-complet podria estar a NP.[3]
Un exemple de problema que se sap que és NP i co-NP és la factorització d'enters: donat dos nombres positius i enters m i n determinar si m té un factor menor que n i més gran que 1. Que pertany a NP és clar: si m te dit factor, llavors el propi factor és un certificat. Que pertanyi a la classe co-NP és també evident: es pot obtenir la llista de factors primers de m, tots més grans o iguals a n, que el verificador pot comprovar si és vàlid per multiplicacions i el test de primalitat AKS. No es coneix cap algorisme per factoritzar en temps polinòmic, i per tant se sap que aquest problema està a NP i co-NP però no se sap si està també a P.
Referències
modifica- ↑ Michael., Sipser,. Introduction to the theory of computation. 3a edició. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790.
- ↑ Peter., Linz,. An introduction to formal languages and automata. 5th ed. Sudbury, MA: Jones & Bartlett Learning, 2012. ISBN 9781449615529.
- ↑ Oded., Goldreich,. P, NP, and NP-completeness : the basics of computational complexity. Cambridge: Cambridge University Press, 2010. ISBN 9780511909443.