NP luokka

Algoritmien teoriassa luokka NP ( englanniksi non-deterministic polynomial ) on joukko ratkaistavuusongelmia , joiden ratkaisu voidaan tarkistaa Turingin koneella ajassa, joka ei ylitä jonkin syötteen koolla olevan polynomin arvoa. tiedot, joidenkin lisätietojen kera (ns. päätöstodistus ) .

Vastaavasti NP-luokka sisältää ongelmia, jotka voidaan ratkaista polynomiajassa epädeterministisellä Turingin koneella .

Tehtävät, joissa on polynomiaikaisia ratkaisualgoritmeja, voidaan ratkaista tietokoneella paljon nopeammin kuin suoralla laskennalla, jonka aika on eksponentiaalinen . Tämä määrittää luokkien P ja NP tasa-arvoongelman käytännön merkityksen .

Määritelmät

Monimutkaisuusluokka NP on määritelty joukolle kieliä eli äärellisen aakkoston sanajoukkoja . Kielen L sanotaan kuuluvan luokkaan NP, jos luokasta P on olemassa kaksipaikkainen predikaatti ( eli polynomiajassa laskettavissa) ja sellainen vakio , että mille tahansa sanalle x ehto " x kuuluu L: lle " on vastaa ehtoa "on y , jonka pituus on pienempi kuin sellainen, että se on tosi " (jossa | x | on sanan x pituus ). Sanaa y kutsutaan sertifikaatiksi , että x kuuluu kieleen L. Siten, jos meillä on sana, joka kuuluu kieleen, ja toinen todistajasana, jonka pituus on rajoitettu (jota voi olla vaikea löytää), voimme nopeasti varmistaa, että x todella kuuluu L:hen . $\Sigma$ $R(x,\,y)$ $c>0$ $|x|^{c}$ $R(x,\,y)$

Vastaava määritelmä voidaan saada käyttämällä epädeterministisen Turingin koneen käsitettä (eli Turingin konetta , jonka ohjelmassa voi olla eri suoria samalla vasemmalla sivulla). Jos kone on kohdannut "haarukan" eli epäselvyyden ohjelmassa, niin erilaiset laskentavaihtoehdot ovat mahdollisia edelleen. Predikaattia , joka edustaa tiettyä epädeterminististä Turingin konetta, pidetään yhtä suurena kuin yksi, jos on vähintään yksi laskentavaihtoehto, joka palauttaa arvon 1, ja nolla, jos kaikki vaihtoehdot palauttavat arvon 0. Jos laskutoimituksen pituus, joka antaa arvon 1, ei ylitä jotakin polynomia pituus x , niin predikaattia kutsutaan kuuluvaksi luokkaan NP. Jos kielellä on predikaatti luokasta NP, joka tunnistaa sen, kielen sanotaan kuuluvan luokkaan NP. Tämä määritelmä vastaa yllä annettua: todistajana voit ottaa laskelman haarukoista haluttujen oksien numerot. Koska kieleen kuuluvalla x :llä koko laskentapolun pituus ei ylitä x :n pituista polynomia , niin todistajan pituutta rajoittaa myös x :n pituinen polynomi . $R(x)$

Mikä tahansa ongelma sanan x kuulumisesta kieleen L , joka on luokassa NP, voidaan ratkaista eksponentiaalisessa ajassa luettelemalla kaikki mahdolliset alle :n pituusvarmenteet . Voit ratkaista sen kvanttitietokoneella GSA :n avulla . Tässä tapauksessa kaikkien mahdollisten lajiteltujen varmenteiden kokonaismäärä voidaan määrittää geometrisen progression jäsenten summan kaavalla, jonka nimittäjä on yhtä suuri kuin aakkosten merkkien määrä ja ensimmäinen jäsen on yhtä suuri kuin 1 : $|x|^{c}$ $|x|^{c}$ $|\Sigma |$ $\Sigma$

$N={\frac {1-|\Sigma |^{|x|^{c}}}{1-|\Sigma |}}$

Siksi Q-bittejä vaaditaan halutun varmenteen etsimiseen GSA-menetelmällä . Todistus löydetään enintään . $\left\lceil \log _{2}{\frac {1-|\Sigma |^{|x|^{c}}}{1-|\Sigma |}}\right\rceil$ $O\left({\sqrt {\frac {1-|\Sigma |^{|x|^{c}}}{1-|\Sigma |}}}\oikea)$

Suhde muihin luokkiin

Kielten luokkaa, joiden komplementit kuuluvat NP:hen, kutsutaan co-NP- luokaksi , vaikka tämän luokan ei ole osoitettu eroavan NP-luokasta. Luokkien NP ja co-NP leikkauspiste sisältää luokan P . Erityisesti luokka NP sisältää luokan P. Tämän sisällyttämisen tiukkuudesta ei kuitenkaan tiedetä mitään.

Luokkien P ja NP tasa-arvoongelma on yksi keskeisistä avoimista ongelmista algoritmien teoriassa. Jos ne ovat yhtä suuret, mikä tahansa NP-luokan tehtävä voidaan ratkaista nopeasti (polynomiajassa). Tiedeyhteisö on kuitenkin taipuvainen kielteiseen vastaukseen tähän kysymykseen. [yksi]

NP-luokka sisältyy muihin, laajempiin luokkiin, kuten PH-luokkaan . Avoimia kysymyksiä on myös sen sisällyttämisen tiukkuuteen muihin luokkiin.

Esimerkkejä luokan NP ongelmista

Voidaan mainita monia ongelmia, joista tällä hetkellä ei tiedetä kuuluuko ne P:hen, mutta tiedetään niiden kuuluvan NP:hen. Heidän keskuudessaan:

Boolen kaavan tyydyttävyysongelma : selvittää annetusta loogisen kaavasta , onko siinä joukko muuttujia, jotka muuttavat sen arvoksi 1. Varmenne on tällainen joukko.
Klikkien ongelma : Kun kaavio on annettu , selvitä, sisältääkö se tietyn kokoisia klikkejä (täydellisiä alikaavioita). Sertifikaatti — klikin muodostavien kärkien lukumäärät.
Hamiltonin syklin esiintymisen määritys graafissa . Sertifikaatti on sarja pisteitä, jotka muodostavat Hamiltonin syklin.
Ei-optimointiversio matkustavan myyjän ongelmasta (onko reittiä, joka ei ole pidempi kuin annettu k:n arvo) on laajennettu ja realistisempi versio edellisestä tehtävästä. Sertifikaatti on tällainen reitti.
Kokonaislukuratkaisun olemassaolo tietylle lineaaristen epäyhtälöiden järjestelmälle. Sertifikaatti on ratkaisu.
Tietyn määrän jakajia puuttuminen siten, että . Sertifikaatit - jakaa luvun alkutekijöihin sekä niiden ensisijaisuusvarmenteita . $m$ $d$ $1<d\leq k$ $m$

Kaikista NP-luokan tehtävistä voidaan erottaa "vaikeimmat" - NP-täydelliset ongelmat . Jos jokin niistä voidaan ratkaista polynomiajassa, niin kaikki luokan NP tehtävät voidaan ratkaista myös polynomiajassa.

Katso myös

Muistiinpanot

↑ William I. Gasarch. P=?NP-kysely. (neopr.) // SIGACT News. - 2002. - T. 33 , nro 2 . - S. 34-47 . - doi : 10.1145/1052796.1052804 .

Kirjallisuus

Thomas H. Kormen ym. Algoritmit: Rakentaminen ja analyysi = Algoritmien johdatus. - 2. painos - M . : "Williams" , 2006. - 1296 s. — ISBN 0-07-013151-1 .
John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Johdatus automaatioteoriaan, kieliin ja laskemiseen. - M . : "Williams" , 2002. - 528 s. - ISBN 0-201-44124-1 .
Etsi tehtäviä. Luokat P ja NP. Älykkyys. NP-Complete Problems Arkistoitu 13. kesäkuuta 2011 Wayback Machinessa
"Johdatus rakenteelliseen monimutkaisuusteoriaan" . Luentokurssi.

Algoritmien monimutkaisuusluokat
Kevyenä pidetty	DLOGTIME AC 0 ACC 0 TC0 [ fi L SL RL NL NC SC CC P P-täydellinen ZPP RP BPP BQP EQP APX
Taitaa olla vaikeaa	U.P. NP NP valmis co-NP co-NP-täydellinen AM M.A. QMA PH ⊕P PP #P #P - IP_ PSPACE PSPACE-täydellinen
Vaikeaksi pidetty	EXPTIME NEXPTIME EXPACE 2-EXPTIME ELEMENTARY R PR RE täytä uudelleen Co-RE Co-RE-complete KAIKKI