Co-NP-täydellinen luokka

Co-NP-täydellinen ongelma  - algoritmien teoriassa ongelma, jonka vastaus on "kyllä" tai "ei" , joka kuuluu luokkaan co-NP , niin että mikä tahansa tämän luokan ongelma voidaan pelkistää siihen polynomiajassa .

Jos P ≠ co-NP, mitään ko-NP-täydellistä ongelmaa ei voida ratkaista polynomiajassa. Jos jokin co-NP-täydellinen ongelma voidaan ratkaista nopeasti , niin nopea algoritmi on olemassa mille tahansa co-NP-luokan ongelmalle.

Mikä tahansa NP-täydellinen ongelma on täyden NP-täydellinen ongelma . On ongelmia, jotka kuuluvat sekä NP -luokkaan että co-NP-luokkaan , kuten mikä tahansa ongelma luokasta P ja tekijöiden muodostusongelma . Samaan aikaan ei tiedetä, osuvatko luokat NP ja co-NP yhteen tai vastaavasti, onko olemassa ongelma, joka on sekä NP- että ko-NP-täydellinen.

Muodollinen määritelmä

Ratkaisettavuusongelma on ko-NP-täydellinen, jos se itse kuuluu luokkaan co-NP ja mikä tahansa muu co-NP- tehtävä on siihen polynomisesti pelkistävissä . Toisin sanoen mille tahansa co-NP-luokan ongelmalle on olemassa algoritmi, joka polynomiajassa muuntaa ongelman syötetiedot ongelman syöttötiedoiksi siten, että vastaus uuteen tehtävään osuu yhteen. vastauksella alkuperäiseen. Siksi, jos ongelmalle on polynomialgoritmi, niin mikä tahansa co-NP-luokan ongelma voidaan ratkaista polynomiajassa.

Esimerkki

Yksi yksinkertainen esimerkki co-NP-täydestä ongelmasta on Boolen kaavan testaus tautologialle . Eli onko annettu kaava totta kaikille muuttujajoukoille. Tämä ongelma liittyy läheisesti tyydyttävyysongelmaan , jossa meidän on selvitettävä, onko olemassa ainakin yksi tällainen muuttujajoukko.

Kirjallisuus

• Cormen T. Leizerson C. Rivest R. Algoritmit: Rakentaminen ja analyysi: Oppikirja: per. englannista. . - Moskovan MTsNMO. Arkistoitu 21. elokuuta 2019 Wayback Machinessa