the first thing to understand is that P and NP classify languages, not problems. Ymmärtääksemme, mitä tämä tarkoittaa, tarvitsemme ensin joitakin muita määritelmiä.
aakkosto on ei-tyhjä äärellinen symbolijoukko.
{01} on aakkosto kuten ASCII-merkistökin. {} ei ole aakkosto, koska se on tyhjä. N (kokonaisluvut) ei ole aakkosto, koska se ei ole äärellinen.
olkoon Σ aakkosto. Äärellisen määrän symboleita Σ: sta muodostavaa järjestettyä yhtymäkohtaa kutsutaan sanalla Σ: n yli.
merkkijono 101 on aakkosten yläpuolella oleva sana {01}. Tyhjä sana (kirjoitetaan usein ε) on sana minkä tahansa aakkoston yläpuolella. Merkkijono penguin on aakkosten yläpuolella oleva sana, joka sisältää ASCII-merkit. Luvun π desimaalimerkintä ei ole sana aakkosten yläpuolella {.0123456789}, koska se ei ole äärellinen.
sanan pituus w, joka kirjoitetaan| w/, on siinä olevien symbolien lukumäärä.
esimerkiksi/hello | = 5 Ja| ε / = 0. Mille tahansa sanalle w | / w / ∈ n ja siten äärellinen.
olkoon Σ aakkosto. Joukko Σ＊ sisältää kaikki sanat Σ: n yli, myös ε: n. Joukko Σ + sisältää kaikki sanat Σ: n yli, pois lukien ε. N ∈ N: lle Σn on sanajoukko, jonka pituus on n.
jokaisella aakkostolla Σ, Σ＊ ja Σ+ ovat äärettömiä numeroituvia joukkoja. ASCII-merkistössä ΣASCII säännölliset lausekkeet .* ja .+ tarkoittavat ΣASCII＊ ja ΣASCII+.
{01}7 on joukko 7-bittisiä ASCII-koodeja {00000000000001111111101}32 on joukko 32 bitin kokonaislukuarvoja.
olkoon Σ aakkosto ja l &osajoukko; Σ＊. L: ää kutsutaan Σ: n ylittäväksi kieleksi.
aakkostolle Σ tyhjä joukko ja Σ＊ ovat triviaaleja kieliä Σ: n yläpuolella. Edellistä kutsutaan usein tyhjäksi kieleksi. Tyhjä kieli {} ja kieli, joka sisältää vain tyhjän sanan {ε} , ovat erilaisia.
osajoukko {01}32, joka vastaa ei-NaN IEEE 754 liukulukuarvoja, on äärellinen kieli.
kielissä voi olla ääretön määrä sanoja, mutta jokainen kieli on laskettavissa. The set of strings {12, …} denoting the integers in decimal notation is an infinite language over the alphabet {0123456789}. Ääretön jousijoukko {23571113, …} alkulukujen merkitseminen desimaalimerkinnällä on niiden oikea osajoukko. Kieli, joka sisältää kaikki säännöllistä lauseketta vastaavat sanat ?\d+\.\d*(?\d+)?, on kieli ASCII-merkistön päällä (tarkoittaa C-ohjelmointikielen määrittelemien kelvollisten liukulukulausekkeiden osajoukkoa).
ei ole kieltä, joka sisältäisi kaikki reaaliluvut (missä tahansa notaatiossa), koska reaalilukujen joukko ei ole laskettavissa.
olkoon Σ aakkosto ja l &osajoukko; Σ＊. Kone d päättää L, jos jokaiselle tulolle w &In; Σ＊ se laskee ominaisfunktion xL(w) äärellisessä ajassa. Karakteristinen funktio määritellään seuraavasti:
χL: Σ＊ → {0, 1} w ↦ 1, w ∈ L 0, otherwise.tällaista konetta kutsutaan decideriksi L: lle.
konemalleja on useita. Yleisin, joka on nykyään käytännön käytössä, on Turingin koneen malli. Turingin koneella on rajaton lineaarinen tallennustila, joka on ryhmittynyt soluihin. Jokaisessa solussa voi olla täsmälleen yksi aakkosten symboli milloin tahansa. Turingin kone suorittaa laskutoimituksensa laskutoimituksen vaiheiden jonona. Jokaisessa vaiheessa se voi lukea yhden solun, mahdollisesti korvata sen arvon ja siirtää luku – /kirjoituspään yhdellä paikalla vasemmalle tai oikealle solulle. Mitä toimintaa kone suorittaa ohjataan rajallinen valtion Automaatti.
satunnaiskäyttökone, jolla on rajalliset ohjeet ja rajaton tallennustila, on toinen Turingin konemallin veroinen konemalli.
tämän keskustelun vuoksi emme häiritse meitä käyttämällämme tarkalla konemallilla, vaan tyydymme pikemminkin toteamaan, että koneella on äärellinen deterministinen Ohjausyksikkö, rajaton tallennustila ja se suorittaa laskutoimituksen laskettavissa olevien vaiheiden jonona.
koska olet käyttänyt sitä kysymyksessäsi, oletan, että tunnet jo ”big-O” – notaation, joten tässä on vain nopea kertaus.
olkoon F: n → funktio. Joukko O(f) sisältää kaikki funktiot g: n → n, joille on olemassa vakiot n0 ∈ n ja C ∈ n siten, että jokaiselle n ∈ N: lle, jonka n > N0, on totta, että g(n) ≤ C f (n).
nyt ollaan valmiita lähestymään todellista kysymystä.
luokka P sisältää kaikki kielet L, joille on olemassa Turingin kone D, joka päättää L: n ja vakion k ∈ n siten, että jokaisen tulon w kohdalla D pysähtyy korkeintaan t (|w/) – vaiheiden jälkeen funktiolle T ∈ O(n ↦ nk).
koska O(n ↦ nk), vaikkakin matemaattisesti oikein, on hankalaa kirjoittaa ja lukea, useimmat ihmiset – ollakseni rehellinen, kaikki paitsi minä – kirjoittavat yleensä yksinkertaisesti O(NK).
huomaa, että sidottu riippuu W: n pituudesta. näin ollen alkulukujen kielelle tehty argumentti on oikea vain unaray-koodauksissa oleville numeroille, joissa luvun w koodauksen| w / pituus on verrannollinen n: ään. kukaan ei koskaan käyttäisi tällaista koodausta käytännössä. Käyttämällä kehittyneempää algoritmia kuin vain kokeilemalla kaikkia mahdollisia tekijöitä, voidaan kuitenkin osoittaa, että alkulukujen kieli pysyy P: ssä, jos tuloluvut on koodattu binääriin (tai mihin tahansa muuhun kantalukuun). (Huolimatta massiivisesta kiinnostuksesta, tämän pystyivät todistamaan vain Manindra Agrawal, Neeraj Kayal ja Nitin Saxena palkitussa paperissa vuonna 2004, joten voit arvata, että algoritmi ei ole kovin yksinkertainen.)
triviaalit kielet {} ja Σ＊ sekä ei-triviaali kieli {ε} ovat ilmeisesti P: ssä (millä tahansa kirjaimella Σ). Voitko kirjoittaa suosikkiohjelmointikielellesi funktioita, jotka ottavat merkkijonon syötteeksi ja palauttavat Boolen, joka kertoo, onko merkkijono sana kielestä kullekin näistä ja todistaa, että funktiollasi on polynomin ajonaikainen monimutkaisuus?
jokainen säännöllinen kieli (säännöllisen lausekkeen kuvaama kieli) on P.
olkoon Σ aakkosto ja l &osajoukko; Σ＊. Kone V, joka ottaa koodatun tuplen, jossa on kaksi sanaa w, c ∈ Σ＊ ja ulostulot 0 tai 1 äärellisen askelmäärän jälkeen, on todentaja L: lle, jos sillä on seuraavat ominaisuudet.
- annettuna (w, c), v: n lähdöt 1 vain jos w ∈ L.
- jokaiselle w ∈ L: lle on olemassa C Σ Σ＊ siten, että V(w, c) = 1.
edellä olevan määritelmän c: tä kutsutaan todistajaksi (tai todistukseksi).
todentaja saa antaa vääriä negatiiveja väärälle todistajalle, vaikka w todellisuudessa olisi L. vääriä positiivisia ei kuitenkaan saa antaa. Vaaditaan myös, että jokaista kielen sanaa kohden on vähintään yksi todistaja.
kielikomposiitille, joka sisältää desimaalikoodaukset kaikista kokonaisluvuista, jotka eivät ole alkulukuja, todistaja voisi olla factorisaatio. Esimerkiksi (659, 709) on todistajana 467231 ∈ komposiitti. Voit helposti tarkistaa, että paperiarkilla ilman todistusta, todistaa, että 467231 ei ole prime olisi vaikeaa ilman tietokonetta.
emme sanoneet mitään siitä, miten sopiva todistaja löytyy. Tämä on ei-deterministinen osa.
Luokka NP sisältää kaikki kielet L, joille on olemassa Turingin kone V, joka verifioi L: n ja vakio k ∈ n siten, että jokaiselle tulolle (w, c) V pysähtyy korkeintaan t (|w/) – vaiheiden jälkeen funktiolle T ∈ O(n ↦ nk).
huomaa, että yllä oleva määritelmä viittaa siihen, että jokaiselle w ∈ L: lle on olemassa todistaja c, jonka| c| ≤ T (|w/). (Turingin kone ei voi mitenkään katsoa enempää todistajan symboleja.)
NP on P: n superjoukko (miksi?). Ei tiedetä, onko olemassa kieliä, jotka ovat NP: ssä mutta eivät P: ssä.
kokonaisluku ei ole kieli sinänsä. Voimme kuitenkin rakentaa kielen, joka edustaa siihen liittyvää päätösongelmaa. Toisin sanoen kieli, joka sisältää kaikki tuplet (n, m) siten, että n: llä on tekijä d, jonka d ≤ m. kutsukaamme tätä KIELIKERROINTA. Jos sinulla on algoritmi päättää tekijä, sitä voidaan käyttää laskea täyden factorization vain polynomi overhead suorittamalla rekursiivinen binary haku kunkin alkutekijä.
on helppo osoittaa, että tekijä on NP. Asianmukainen todistaja olisi yksinkertaisesti itse tekijä d, ja todentajan olisi vain todennettava, että D ≤ m ja n mod d = 0. Kaikki tämä voidaan tehdä polynomiaikana. (Muista jälleen, että koodauksen pituus ratkaisee ja se on logaritminen n.)
Jos voit osoittaa, että tekijä on myös P, voit olla varma saada monia hienoja palkintoja. (Ja olet rikkonut merkittävän osan nykypäivän salausta.)
jokaiselle NP: n kielelle on olemassa brute-force-algoritmi, joka päättää sen deterministisesti. Se yksinkertaisesti suorittaa tyhjentävän haun kaikista todistajista. (Huomaa, että todistajan enimmäispituutta rajoittaa polynomi. Algoritmisi päättämään alkulukuja oli brute-force-algoritmi komposiittien päättämiseksi.
voidaksemme vastata viimeiseen kysymykseenne, meidän on otettava käyttöön vähennys. Vähennykset ovat hyvin voimakas käsite teoreettisessa tietojenkäsittelytieteessä. Yhden ongelman vähentäminen toiseen merkitsee pohjimmiltaan yhden ongelman ratkaisemista toisen ongelman ratkaisemisen avulla.
olkoon Σ kirjaimisto ja A ja B kielet Σ. A on polynomiaikainen moniyksityinen B: hen, jos on olemassa funktio f: Σ＊ → Σ＊ , jolla on seuraavat ominaisuudet.
- w ∈ A f f(w) ∈ B kaikille W ∈ Σ＊.
- funktio f voidaan laskea Turingin koneella jokaiselle tulolle w useissa portaissa, joita rajoittaa polynomi in|w/.
tällöin kirjoitetaan A ≤p B.
esimerkiksi olkoon a kieli, joka sisältää kaikki kolmion sisältävät graafit (koodattu adjukenssimatriisiksi). (Kolmio on sykli pituus 3.) Olkoon edelleen B kieli, joka sisältää kaikki matriisit, joiden jälki ei ole nolla. (Matriisin jälki on sen tärkeimpien diagonaalielementtien summa.) Sitten A on polynomi-aika monta-yksi reducible B. Tämän todistamiseksi meidän on löydettävä sopiva muunnosfunktio f.tässä tapauksessa voimme asettaa f laskemaan adjacency matriisin 3. potenssiin. Tämä edellyttää kahta matriisi-matriisituotetta, joista jokaisella on polynomin kompleksisuus.
on triviaalisesti totta, että L ≤p L. (voitko todistaa sen muodollisesti?)
sovellamme tätä NP: hen nyt.
a kieli L on NP-kova, jos ja vain jos L’ ≤p L jokaiselle kielelle L’ ∈ NP.
NP-kova kieli voi olla NP: ssä itsessään tai ei.
kieli L on NP-täydellinen, jos ja vain jos
- l ∈ NP ja
- L on NP-kova.
tunnetuin NP-täydellinen kieli on SAT. Se sisältää kaikki Boolen kaavat, jotka voidaan tyydyttää. Esimerkiksi (A ∨ B) ∧ (A ∨ b) ∈ SAT. Kelvollinen todistaja on {a = 1, b = 0}. Kaava (A ∨ b) ∧ (A ∨ b) ∧ B SAT SAT. (Miten todistaisit sen?)
ei ole vaikea osoittaa, että SAT ∈ NP. SAT: n NP-kovuuden osoittaminen on melkoista työtä, mutta sen teki vuonna 1971 Stephen Cook.
kun yksi NP-täydellinen kieli oli tiedossa, oli suhteellisen yksinkertaista osoittaa muiden kielten NP-täydellisyys pelkistyksellä. Jos kielen A tiedetään olevan NP-kova, niin osoittamalla, että A ≤p B osoittaa, että B on myös NP-kova (transitiivisuuden kautta ”≤p”). Vuonna 1972 Richard Karp julkaisi luettelon 21 kielestä, jotka hän voisi osoittaa NP-complete kautta (transitiivinen) vähentäminen SAT. (Tämä on ainoa paperi tässä vastauksessa, että itse suosittelen sinun pitäisi lukea. Toisin kuin muut, se ei ole vaikea ymmärtää ja antaa erittäin hyvän käsityksen siitä, miten todistaa NP-täydellisyyden kautta vähentäminen toimii.)
lopuksi lyhyt yhteenveto. Käytämme tunnuksia NPH ja NPC kuvaamaan NP-hard-ja NP-complete-kielten luokkia.
- p ⊆ NP
- NPC &osajoukko; Np ja NPC &osajoukko; NPH, oikeastaan NPC = NP ∩ NPH määritelmän mukaan
- (a ∈ NP) ∧ (B ∈ NPH) ⇒ a ≤p b
huomaa, että Inkluusio NPC &osajoukko; np on asianmukainen myös siinä tapauksessa, että P = NP. Tämän ymmärtääksesi tee itsellesi selväksi, että mitään ei-triviaalia kieltä ei voida pelkistää triviaaliksi ja että P: ssä on triviaaleja kieliä samoin kuin NP: ssä ei-triviaaleja kieliä. Tämä on (ei kovin kiinnostava) kulmatapaus kuitenkin.
ensisijainen sekaannuksen lähde näyttää olevan se, että ajattelit ”n” in ”O(n ↦ f(n))” tulkintana algoritmin syötöstä, kun se todellisuudessa viittaa syötön pituuteen. Tämä on tärkeä ero, koska se tarkoittaa, että algoritmin asymptoottinen monimutkaisuus riippuu syötteelle käytetystä koodauksesta.
tällä viikolla saavutettiin uusi ennätys suurimmasta tunnetusta Mersennen alkuluvusta. Suurin nykyisin tunnettu alkuluku on 274 207 281 − 1. Tämä numero on niin valtava, että se antaa minulle päänsärkyä, joten käytän pienempää seuraavassa esimerkissä: 231 – 1 = 2 147 483 647. Se voidaan koodata eri tavoin.
- sen Mersennen eksponentin mukaan desimaalilukuna:
31(2 tavua) - desimaalilukuna:
2147483647(10 tavua) - unaarisena lukuna:
11111…11missä…on korvattava 2 147 483 640 lisää1s (lähes 2 gib)
kaikki nämä merkkijonot koodaavat saman numeron ja koska jokin näistä, voidaan helposti rakentaa mikä tahansa muu saman numeron koodaus. (Desimaalikoodauksen voi halutessaan korvata binäärisellä, oktaalisella tai heksadesimaalisella. Se muuttaa pituutta vain vakiokertoimella.)
naiivi algoritmi primaalisuuden testaamiseen on vain polynomi unaarisille koodauksille. AKS: n alkeiskoe on polynomi desimaalille (tai jollekin muulle emäkselle B ≥ 2). Lucas-Lehmerin alkeiskoe on tunnetuin algoritmi Mersennen primes Mp: lle, jossa p on pariton alkuluku, mutta se on silti eksponentiaalinen Mersennen eksponentin p (polynomin P) binäärikoodauksen pituudessa.
Jos haluamme puhua algoritmin monimutkaisuudesta, on erittäin tärkeää, että olemme hyvin selvillä siitä, mitä edustusta käytämme. Yleisesti voidaan olettaa, että käytössä on tehokkain koodaus. Toisin sanoen binäärinen kokonaisluvuille. (Huomaa, että jokainen alkuluku ei ole Mersennen alkuluku, joten Mersennen eksponentin käyttäminen ei ole yleinen koodausjärjestelmä.)
teoreettisessa kryptografiassa monet algoritmit ohittavat muodollisesti täysin hyödyttömän merkkijonon k 1s ensimmäisenä parametrina. Algoritmi ei koskaan katso tätä parametria, mutta sen avulla se voi olla muodollisesti polynomi K: ssa, joka on menettelyn turvallisuuden virittämiseen käytetty tietoturvaparametri.
joissakin ongelmissa, joissa päätöskieli binäärikoodauksessa on NP-täydellinen, päätöskieli ei ole enää NP-täydellinen, jos sulautettujen numeroiden koodaus vaihdetaan unaryyn. Muiden ongelmien ratkaisukielet pysyvät NP-täydellisinä silloinkin. Jälkimmäisiä kutsutaan voimakkaasti NP-täydellisiksi. Tunnetuin esimerkki on bin packing.
on myös (ja ehkä enemmänkin) mielenkiintoista nähdä, miten algoritmin monimutkaisuus muuttuu, jos tulo pakataan. Esimerkiksi Mersennen alkuluvuista on nähty kolme koodausta, joista jokainen on logaritmisesti edeltäjäänsä pakatumpi.
vuonna 1983 Hana Galperin ja Avi Wigderson ovat kirjoittaneet mielenkiintoisen tutkielman yhteisten graafialgoritmien monimutkaisuudesta, kun kuvaajan tulokoodaus pakataan logaritmisesti. Näiden panosten, kieli kaaviot sisältävät kolmion ylhäältä (jossa se oli selvästi P) yhtäkkiä tulee NP-täydellinen.
ja tämä johtuu siitä, että kieliluokat kuten P ja NP on määritelty kielille, ei ongelmille.