co-NP - co-NP
I beregningskompleksitetsteori er co-NP en kompleksitetsklasse . Et avgjørelsesproblem X er medlem av co-NP hvis og bare hvis komplementet X er i kompleksitetsklassen NP . Klassen kan defineres som følger: et beslutningsproblem er i co-NP nettopp hvis bare ingen -forekomster har et " sertifikat " med polynomlengde, og det er en polynom- tidsalgoritme som kan brukes til å verifisere ethvert påstått sertifikat.
Det vil si, co-NP er settet med beslutningsproblemer hvor det eksisterer et polynom p (n) og et polynom-tids avgrenset Turing maskin M slik at for hvert eksempel x , x er en ikke -instance hvis og bare hvis: for noen mulig sertifikat c av lengde avgrenset av p (n) , godtar Turing-maskinen M paret ( x , c ).
Utfyllende problemer
Mens et NP-problem spør om en gitt forekomst er en ja- instans, spør komplementet om en forekomst er en nei- instans, noe som betyr at komplementet er i co-NP. Enhver ja -instans for det opprinnelige NP-problemet blir en nei- instans for komplementet, og omvendt.
Utilfredsstillelse
Et eksempel på et NP-komplett problem er det boolske tilfredsstillelsesproblemet : gitt en boolsk formel, er det tilfredsstillende (er det en mulig inngang som formelen gir sant for)? Det komplementære problemet spør: "Gitt en boolsk formel, er den utilfredsstillende (gjør alle mulige innganger til formelen falske)?". Siden dette er komplementet til tilfredsstillelsesproblemet, er et sertifikat for en nei- innstilling det samme som for et ja- innlegg fra det opprinnelige NP-problemet: et sett med boolske variabeltilordninger som gjør formelen sann. På den annen side vil et sertifikat for ja- innstilling for det komplementære problemet være like komplisert som nei- innføringen av det opprinnelige NP-tilfredsstillelsesproblemet.
Dobbelte problemer
co-NP-fullstendighet
Et problem L er co-NP-komplett hvis og bare hvis L er i co-NP og for eventuelle problem i co-NP, eksisterer det en polynomisk tid reduksjon fra det problemet til L .
Tautologi Reduksjon
Å bestemme om en formel i proposisjonslogikk er en tautologi er co-NP-komplett: det vil si om formelen evalueres til sann under alle mulige tilordninger til variablene.
Forhold til andre klasser
P , klassen av polynomiske tidsløsbare problemer, er en delmengde av både NP og co-NP. P antas å være en streng delmengde i begge tilfeller (og kan beviselig ikke være streng i det ene tilfellet og ikke streng i det andre tilfellet).
NP og co-NP antas også å være ulik. I så fall kan ikke noe NP-komplett problem være i co-NP, og ingen co-NP-komplett problem kan være i NP. Dette kan vises som følger. Anta at det for motsigelsen eksisterer et NP-komplett problem X som er i co-NP. Siden alle problemer i NP kan reduseres til X , følger det at for hvert problem i NP kan vi konstruere en ikke-deterministisk Turing-maskin som bestemmer dens komplement i polynomisk tid; dvs. NP ⊆ co-NP. Av dette følger det at settet med komplement til problemene i NP er en delmengde av settet med komplement til problemene i co-NP; dvs. co-NP ⊆ NP. Dermed co-NP = NP. Beviset for at ingen co-NP-komplett problemer kan være i NP hvis NP ≠ co-NP er symmetrisk.
Heltalsfaktorisering
Et eksempel på et problem som er kjent for å tilhøre både NP og co-NP (men ikke kjent for å være i P) er heltallfaktorisering : gitt positive heltall m og n , avgjør om m har en faktor mindre enn n og større enn en . Medlemskap i NP er klart; hvis m har en slik faktor, er faktoren i seg selv et sertifikat. Medlemskap i co-NP er også greit: man kan bare oppgi de viktigste faktorene til m , alle større eller lik n , som verifisereren kan bekrefte å være gyldig ved multiplikasjon og AKS-test . Det er foreløpig ikke kjent om det er en polynom-tidsalgoritme for faktorisering, tilsvarende at heltallfaktorisering er i P, og derfor er dette eksemplet interessant som et av de mest naturlige problemene som er kjent for å være i NP og co-NP, men ikke kjent for være i P.
