NP on kielten luokka, joilla on polynomiaikaiset varmentajat
Luokka NP, joka tarkoittaa "ei-determinististä polynomiaikaa", on laskennallisen monimutkaisuuden teorian peruskäsite, joka on teoreettisen tietojenkäsittelytieteen alakenttä. NP:n ymmärtämiseksi on ensin ymmärrettävä päätösongelmien käsite, jotka ovat kysymyksiä, joihin on vastaus kyllä tai ei. Kielellä tässä yhteydessä tarkoitetaan merkkijonojoukkoa jonkin aakkoston yli, jossa jokainen merkkijono koodaa päätösongelman esiintymän.
Kielen (L) sanotaan olevan NP:ssä, jos kielelle (L) on olemassa polynomiaikainen todentaja. Todentaja on deterministinen algoritmi (V), joka ottaa kaksi syötettä: esiintymän (x) ja varmenteen (y). Todistus (y) tunnetaan myös "todistajana" tai "todisteena". Todentaja (V) tarkistaa, vahvistaako varmenne (y), että (x) kuuluu kieleen (L). Muodollisesti kieli (L) on NP:ssä, jos on olemassa polynomi-aika-algoritmi (V) ja polynomi (p(n)) siten, että jokaiselle merkkijonolle (x L:ssä) on olemassa merkkijono (y), jossa on ( |y|. leq p(|x|)) ja (V(x, y) = 1). Sitä vastoin jokaiselle merkkijonolle (x ei L) ei ole merkkijonoa (y), joka olisi (V(x, y) = 1).
Tämän käsitteen selventämiseksi harkitse hyvin tunnettua "Boolean satisfiability" (SAT) -ongelmaa. SAT-ongelma kysyy, onko tietyssä Boolen kaavassa muuttujille määritetty totuusarvot siten, että kaava evaluoituu todeksi. SAT-ongelma on NP:ssä, koska Boolen kaavan ( phi ) ja sen muuttujien totuusarvojen antamisen ( alfa ) perusteella voidaan polynomiajassa varmistaa, täyttääkö ( alpha ) ( phi ). Tässä ilmentymä ( x ) on Boolen kaava ( phi ) ja varmenne ( y ) on tehtävä ( alfa ). Todentaja ( V ) tarkistaa tekeekö ( alfa ) ( phi ):n tosi, mikä voidaan tehdä polynomiajassa suhteessa ( phi ) kokoon.
Toinen havainnollistava esimerkki on "Hamiltonin polun" ongelma. Tämä ongelma kysyy, onko tietyssä kaaviossa polkua, joka vierailee kussakin kärjessä täsmälleen kerran. Hamiltonin polun ongelma on myös NP:ssä, koska graafin ( G ) ja kärkijonon ( P ) perusteella voidaan polynomiajassa varmistaa, onko ( P ) Hamiltonin polku kohdassa ( G ). Tässä tapauksessa ilmentymä ( x ) on graafi ( G ) ja varmenne ( y ) on pisteiden sarja ( P ). Todentaja ( V ) tarkistaa, muodostaako ( P ) Hamiltonin polun, mikä voidaan tehdä polynomiajassa suhteessa ( G ) kokoon.
Polynomiaikaisen todennettavuuden käsite on tärkeä, koska se tarjoaa tavan karakterisoida ongelmia, jotka ovat tehokkaasti tarkistettavissa, vaikka ratkaisun löytäminen olisikin laskennallisesti mahdotonta. Tämä johtaa kuuluisaan kysymykseen, onko ( P = NP ), joka kysyy, voidaanko jokainen ongelma, jonka ratkaisu voidaan varmistaa polynomiajassa, myös ratkaista polynomiajassa. Luokka ( P ) koostuu päätöstehtävistä, jotka voidaan ratkaista polynomiajassa deterministisellä Turingin koneella. Jos ( P = NP ), se tarkoittaisi, että jokaisella polynomiaikaisen todentajan tehtävällä on myös polynomiaikainen ratkaisija. Tämä kysymys on edelleen yksi tietojenkäsittelytieteen tärkeimmistä avoimista ongelmista.
Yksi NP:n tärkeimmistä ominaisuuksista on, että se on suljettu polynomiaikaisten pelkistysten alla. Polynomiaikainen pelkistys kielestä ( L_1 ) kieleen ( L_2 ) on polynomiaikaisesti laskettava funktio ( f ) siten, että ( x L_1 ) jos ja vain jos ( f(x) L_2 :ssa). Jos on olemassa polynomiaikainen pelkistys arvosta (L_1) arvoon (L_2) ja (L_2) on NP:ssä, niin (L_1) on myös NP:ssä. Tämä ominaisuus on tärkeä NP-täydellisyyden tutkimuksessa, joka tunnistaa NP:n "vaikeimmat" ongelmat. Ongelma on NP-täydellinen, jos se on NP:ssä ja jokainen NP:n tehtävä voidaan pelkistää siihen polynomiajassa. SAT-ongelma oli ensimmäinen NP-täydelliseksi todistettu ongelma, ja se toimii perustana muiden ongelmien NP-täydellisyyden todistamiselle.
Polynomiaikaisen todennettavuuden käsitteen havainnollistamiseksi tarkemmin harkitse "osajoukon summa" -tehtävää. Tämä ongelma kysyy, onko annetusta kokonaislukujoukosta olemassa alijoukko, joka summautuu määritettyyn kohdearvoon. Osajoukon summa -ongelma on NP:ssä, koska kun on annettu joukko kokonaislukuja ( S ), tavoitearvo ( t ) ja ( S ) osajoukko ( S' ), voidaan polynomiajassa tarkistaa, onko alkioiden summa (S') on yhtä kuin (t). Tässä ilmentymä (x) on pari ((S, t)) ja varmenne (y) on osajoukko (S'). Todentaja (V) tarkistaa, onko (S'):n alkioiden summa yhtä kuin (t), mikä voidaan tehdä polynomiajassa suhteessa (S) kokoon.
Polynomiaikaisen todennettavuuden merkitys ulottuu teoreettisten näkökohtien ulkopuolelle. Käytännössä se tarkoittaa, että NP:n ongelmille, jos ehdotettu ratkaisu (sertifikaatti) tarjotaan, se voidaan tarkistaa tehokkaasti. Tällä on merkittäviä vaikutuksia salausprotokolliin, optimointiongelmiin ja eri aloille, joilla ratkaisun oikeellisuuden varmistaminen on tärkeää.
Yhteenvetona voidaan todeta, että luokka NP kattaa päätösongelmat, joille ehdotettu ratkaisu voidaan varmistaa polynomiajassa deterministisellä algoritmilla. Tämä käsite on laskennallisen monimutkaisuuden teorian perusta, ja sillä on syvällisiä vaikutuksia sekä tietojenkäsittelytieteen teoreettisiin että käytännön näkökohtiin. NP:n, polynomiaikaisen todennettavuuden ja niihin liittyvien käsitteiden, kuten NP-täydellisyyden, tutkimus on edelleen elinvoimainen ja kriittinen tutkimusalue.
Muita viimeaikaisia kysymyksiä ja vastauksia liittyen NP: n ja polynomisen todennettavuuden määritelmä:
- Voiko ongelma olla NP-kompleksisuusluokassa, jos on olemassa epädeterministinen turing-kone, joka ratkaisee sen polynomiajassa
- Onko NP:n määritelmä polynomiaikaisten todentajien päätösongelmien luokkana ja sen välillä, että luokan P ongelmissa on myös polynomiaikaisia todentajia?
- Onko P-luokan todentaja polynomi?
- Mitä eroa on laskennallisen kompleksisuusteorian luokilla P ja NP, ja miten ne liittyvät kielten jäsenyyden päättämisen ja todentamisen käsitteisiin?
- Kuvaa prosessi polynomiaikaisen epädeterministisen Turingin koneen muodostamiseksi.
- Kuinka polynomiaikatodentaja voidaan muuntaa vastaavaksi epädeterministiseksi Turingin koneeksi?
- Selitä luokan NP kaksi ekvivalenttia määritelmää ja kuinka ne liittyvät polynomiaikaisiin todentajiin ja ei-deterministisiin Turingin koneisiin.
- Mitä on polynomivarmennettavuus ja miten se liittyy luokkaan NP?