Olet periaatteessa oikeassa P: ssä ja NP: ssä, mutta et NP-hardissa ja NP-complete: ssa.

Aloittelijoille tässä kyseisten neljän monimutkaisuusluokan ytimekkäät määritelmät:

• P on päätösongelmien luokka, joka voidaan ratkaista polynomiajassa deterministisellä Turingin koneella.

• NP on päätösongelmien luokka, joka voidaan ratkaista polynomiajassa ei-deterministisellä Turingin koneella. Vastaavasti se on ongelmaluokka, joka voidaan todentaa polynomiajassa deterministisen Turingin koneen avulla.

• NP-hard on päätösongelmien luokka, johon kaikki NP: n ongelmat voidaan kohdistaa deterministinen Turingin kone pienentää polynomiaikaan.

• NP-täydellinen on NP-kovan ja NP: n leikkauspiste. Vastaavasti NP-täydellinen on NP: n päätösongelmien luokka, johon kaikki muut NP: n ongelmat voidaan vähentää polynomiajassa deterministisen Turingin koneen avulla.

Ja tässä ”sa Eulerin kaavio Wikipediasta , joka näyttää näiden neljän luokan väliset suhteet (olettaen, että P ei ole yhtä suuri kuin NP):

Osa, jonka oletan olevan sinulle tuntematon tai sekaisin on käsite ”polynomiajan lyhennys” ongelmasta X ongelmaan Y. Pienentäminen X: stä Y: ksi on yksinkertaisesti algoritmi A, joka ratkaisee X: n käyttämällä jotakin muuta algoritmia B, joka ratkaisee ongelman Y. Tätä pelkistystä kutsutaan ” polynomiajan vähennys ”, jos A: n kaikilla muilla osilla kuin B on polynominen aikakompleksi. Triviaalina esimerkkinä matriisin pienimmän elementin löytämisongelma on vakioaika pelkistettävä lajitteluongelmaksi, koska voit lajitella matriisin ja palauttaa sitten lajitellun matriisin ensimmäisen elementin.

Yksi asia, joka on helppo jättää huomiotta NP-hard-määritelmässä, on se, että vähennys siirtyy NP-ongelmista NP-hard -ongelmiin, mutta ei välttämättä päinvastoin . Tämä tarkoittaa, että NP-hard -ongelmat voivat olla NP: ssä tai paljon korkeammassa monimutkaisuusluokassa (kuten voit nähdä Euler-kaaviosta), tai ne eivät ehkä edes ole ratkaistavia ongelmia.Siksi ihmiset sanovat usein jotain ”NP-hard tarkoittaa ainakin yhtä kovaa kuin NP” yrittäessään selittää tätä asiaa epävirallisesti.

Pysäytysongelma on hyvä esimerkki NP-kovasta ongelmasta, joka ”Ei selvästikään NP: ssä, kuten Wikipedia selittää :

Se on helppo todistaa, että pysäytysongelma on NP-vaikea, mutta ei NP-täydellinen. Esimerkiksi Boolen tyydyttävyysongelma voidaan vähentää pysähtymisongelmaksi muuttamalla se kuvaukseksi Turingin koneesta, joka yrittää kaikki totuusarvomääritykset ja kun se löytää tyydyttävän kaavan, jonka se pysäyttää ja muuten se menee äärettömään silmukkaan. On myös helppo nähdä, että pysäytysongelma ei ole NP: ssä, koska kaikki NP: n ongelmat voidaan ratkaista rajallisessa määrin operaatioita, kun taas pysäytysongelma on yleensä ratkaisematon.

Kommentit

• @Nakano Intuitiivisesti, se ’ sa ” vähentäminen ” siinä mielessä, että yhdestä ongelmasta tehdään jonkin toisen ongelman osaongelma. Se, että jotkut näistä vähennyksistä lisäävät monimutkaisuutta sen sijaan, että vähentävät sitä tekemällä huonon valinnan ” aliprobleemista ” tarkoittaa yksinkertaisesti sitä, ettet koskaan käytä näitä vähennyksiä missä tahansa reaalimaailman koodissa. Vaikka olenkin rehellinen, NP-hard vaikuttaa minusta oudolta eikä kovin mielenkiintoiselta luokalta; voi olla hedelmällisempää jättää se huomiotta ja ajatella vain NP-täydellinen kuin joukko NP-ongelmia, joihin kaikki muut NP-ongelmat vähentävät.
• @Nakano stackoverflow.com/questions/12637582/… Uskon, että lyhyt vastaus on, että kun ihmiset puhuvat kokonaislukukertoimen olevan NP, he ’ puhuu normaalisti todella suurista kokonaisluvuista, joille alat yleensä tehdä isoja O-todisteita n: llä ” kuinka monta kokonaislukua muistissa on bittejä ” funktioon ” syötettyjen kokonaislukujen sijasta ”.
• @Nakano: Suuressa O-merkinnässä n on mitata syötteen kokoa (elementtien, tavujen, numeroiden jne. Lukumäärä), ei arvon panos.
• @Nakano Lyhyt vastaus on, että olet ’ kaikki kunnossa, ja siksi kun teet aikaa mplexity-analyysi sinun on aina määritettävä, mitä n tarkoittaa . Väite, että n on ” syötteen koko ”, on vain tiivis yhteenveto siitä, miten normaalisti päätämme määritellä n. Se ’ ei ole osa big-O-notaation tai aikakompleksin tarkkoja määritelmiä. Uskon, että olet oikeassa sanotessasi, että kokonaislukukerroin on O (sqrt (n)), kun n on syötteen arvo . Sattuu niin, että monimutkaisuuden tulokset, joissa n tarkoittaa kokoa, ovat käytännössä paljon hyödyllisempiä kuin ne, joissa n tarkoittaa arvoa.
• @Nakano It ’ On myös syytä pitää mielessä, että teknisesti sinun on määriteltävä myös primitiivisten toimintojesi aikakompleksi (summaus, moninkertaistaminen, lukeminen muistista, kirjoittaminen muistiin, kahden numeron vertaaminen). Suurimman osan ajasta joko oletamme, että kaikki nämä primitiivit ovat vakioita tai laskemme vain yhden tyyppisen operaation (esim. Laskemme algoritmeja perinteisesti vertailut). Epäilen, että kokonaislukutoimituksen tulokset eivät ’ t oleta, että kaikki nämä operaatiot ovat vakioaikaisia kuten tavallisesti, muuten numeron koko ei ’ t: llä on merkitystä.

Kokonaislukukerroin mainitaan esimerkkinä NP: stä, mutta en ymmärrä, miksi se ei ole henkilökohtaisesti P, koska kokeilutekijöihin kuluu O (sqrt (n)) aikaa.

Monimutkaisuusluokkia varten n on syötteen pituus. Joten jos haluat kertoa kokonaisluvun k, n ei ole k, vaan log k, bittien määrä (tai mikä tahansa), joka tarvitaan luvun kirjoittamiseen. Joten kokonaislukukerroin on O(sqrt(k)) kuten sanot, mutta tämä on O(sqrt(2n)), joka on O(2(n/2)).

Oletan, että NP-Hard on vain täynnä tuntemattomia. Vaikea tarkistaa, vaikea ratkaista.

Ei. NP-Hard on vain siitä, kuinka vaikea ongelma on ratkaista.

NP-Hard-ongelmat ovat ainakin vaikeita NP: n vaikeimpina ongelmina. Tiedämme, että ne ovat ainakin niin vaikeita, koska jos meillä olisi polynomi-aikainen algoritmi NP-Hard-ongelmaan, voimme mukauttaa kyseisen algoritmin mihin tahansa NP: n ongelmaan.

NP-Complete En ymmärrä ollenkaan

NP- Täydellinen tarkoittaa, että ongelma on sekä NP että NP-Hard. Se tarkoittaa, että voimme varmistaa ratkaisun nopeasti (NP), mutta se on ainakin yhtä vaikea kuin NP: n vaikein ongelma (NP-Hard).

En todellakaan tiedä, mitä se tarkoittaa, että se ei ole deterministinen.

Ei -determinismi on vaihtoehtoinen määritelmä NP: lle. Ei-deterministinen turing-kone pystyy tosiasiallisesti kopioimaan itsensä milloin tahansa ja saa jokaisen kaksoiskappaleen kulkemaan eri toteutuspolun. Tämän määritelmän mukaan NP on joukko ongelmia, jotka tietokone voi ratkaista polynomiajassa, kuin jotka voivat vapaasti kopioida itseään. On käynyt ilmi, että tämä on täsmälleen sama ongelmajoukko, joka voidaan vahvistaa polynomiajassa.

Kommentit

• Joten se on mahdollista $ O ( n ^ k) $ time -algoritmit NP-ongelmiksi?
• k on vakio reaaliluku? Joo. Kaikki P-ongelmat ovat myös NP-ongelmia. On selvää, että kaikki, mitä voit ratkaista polynomiajassa, voidaan vahvistaa myös polynomiajassa.
• Kuinka pituus / koko määritellään tässä? Esimerkiksi voisin vain kirjoittaa $ n $ isoon pohjaan ja pienentää sen pituutta kirjoitettaessa. Entä ongelmat, jotka eivät ’ t käsittele nimenomaisesti kokonaislukuja, mutta sanovat kaaviot, joissa on $ V $ -pisteet ja $ E $ -reunat jne.
• @Nakano, oikeastaan suuri perusta ei muuta ’ t sitä, koska se olisi vain vakioeroero. Joten se ei vaikuta ’ t polynomiin verrattuna ei-polynomiin. Jos kuitenkin kirjoitit numeron unaarisena, se muuttaisi sitä.
• @Nakano, hmm … En halua ’ ei uskalla yrittää selittää monimutkaisuutta. luokista viisivuotiaille. : P

Ensiksi on ymmärrettävä, että P ja NP luokittele kielet , ei ongelmat . Tarvitsemme ensin joitain muita määritelmiä ymmärtääksemme, mitä tämä tarkoittaa.

aakkoset on ei-tyhjä äärellinen symbolijoukko.

{0 , 1} on aakkoset samoin kuin ASCII-merkistö. {} ei ole aakkoset, koska se on tyhjä. N (kokonaisluvut) ei ole aakkoset, koska se ei ole äärellinen.

Olkoon Σ olla aakkoset. Äärimmäisen määrän symboleita, jotka on liitetty Σ , kutsutaan sanaksi yli Σ .

Merkkijono 101 on aakkoset {0, 1}. tyhjä sana (kirjoitetaan usein nimellä ε ) on sana minkä tahansa aakkosen päällä. Merkkijono penguin on ASCII-merkkejä sisältävä aakkoset. Luvun desimaalimerkintä π ei ole sana aakkosissa {., 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, koska se ei ole rajallinen.

sanan w , joka on kirjoitettu nimellä | w |, pituus on symbolien lukumäärä siinä.

Esimerkiksi | hello | = 5 ja | ε | = 0. Mikä tahansa sana w , | w | ∈ N ja siksi äärellinen.

Anna Σ olla aakkoset. Joukko Σ ^＊ sisältää kaikki sanat Σ , mukaan lukien ε . Joukko Σ ⁺ sisältää kaikki Σ , lukuun ottamatta ε . Mille n ∈ N , Σ ⁿ on joukko sanoja, joiden pituus on n .

jokainen aakkoset Σ , Σ ^＊ ja Σ ⁺ ovat äärettömiä laskettavissa olevat sarjat .ASCII-merkistöryhmille Σ _ASCII säännölliset lausekkeet .* ja .+ merkitse Σ _ASCII ^＊ ja Σ _ASCII ⁺ .

{0, 1} ⁷ on 7-bittisten ASCII-koodien joukko {0000000, 0000001,…, 1111111}. {0, 1} ³² on 32-bittisten kokonaislukuarvojen joukko.

Olkoon Σ aakkoset ja L ⊆ Σ ^＊ . L kutsutaan kieleksi yli Σ .

Aakkosille Σ tyhjä joukko ja Σ ^＊ ovat merkityksettömiä kieliä Σ . Ensimmäistä kutsutaan usein tyhjäksi kieleksi . Tyhjä kieli {} ja vain tyhjää sanaa { ε } sisältävä kieli ovat erilaiset.

{0, 1} ³² , joka vastaa ei-NaN IEEE 754 -liukulukuarvoja, on äärellinen kieli.

Kielillä voi olla ääretön määrä sanoja, mutta jokainen kieli on laskettavissa. Merkkijonojen joukko {1, 2,…}, jotka merkitsevät kokonaislukuja desimaalimerkinnöissä, on ääretön kieli aakkosten {0, 1, 2, 3, 4, 5, 6, 7 , 8, 9}. Ääretön merkkijono {2, 3, 5, 7, 11, 13,…}, jotka merkitsevät alkuluvut desimaalimerkinnöissä, on niiden oikea alijoukko. Kieli, joka sisältää kaikki säännöllisen lausekkeen [+-]?\d+\.\d*([eE][+-]?\d+)? vastaavat sanat, on ASCII-merkistöön kuuluva kieli (merkitsee osaa C-ohjelmointikielen määrittelemistä kelvollisista liukulausekkeista). / p>

Ei ole kieltä, joka sisältäisi kaikkia reaalilukuja (missään merkinnässä), koska reaalilukujoukkoa ei voida laskea.

Anna Σ olla aakkoset ja L ⊆ Σ ^＊ . Kone D päättää L jos jokaiselle tulolle w ∈ Σ ^＊ se laskee ominaisuusfunktion χ _L ( w ) rajallisessa ajassa. Ominaisfunktio määritellään seuraavasti:

χL: Σ＊ → {0, 1} w ↦ 1, w ∈ L 0, otherwise.

Tällaista konetta kutsutaan päättäjäksi kohteelle L . Kirjoitamme ” D ( w ) = x ” sanalle ”annettu w , D lähdöt x ”.

Konemalleja on monia. Yleisin käytännön käytössä oleva malli on Turing-kone . Turingin koneessa on rajoittamaton lineaarinen varastointi, joka on ryhmitelty soluihin. Jokaisessa solussa voi olla täsmälleen yksi aakkosmerkki milloin tahansa. Turingin kone suorittaa laskennan laskentavaiheiden jaksona. Kussakin vaiheessa se voi lukea yhden solun, mahdollisesti korvata sen arvon ja siirtää luku- / kirjoituspäätä yhdellä paikalla vasemmalle tai oikealle solulle. Minkälaista toimintoa kone suorittaa, ohjaa rajallisen tilan automaatti.

Satunnaiskäyttöinen kone, jolla on rajallinen joukko käskyjä ja rajoittamaton tallennustila, on toinen konemalli, joka on yhtä tehokas kuin Turingin konemalli.

Tämän keskustelun vuoksi emme häiritse meitä käyttämällämme tarkalla konemallilla, vaan pikemminkin riittää sanomaan, että koneessa on rajallinen deterministinen ohjausyksikkö, rajoittamaton tallennustila ja se suorittaa laskennan vaiheina se voidaan laskea.

Koska olet käyttänyt sitä kysymyksessäsi, oletan, että olet jo perehtynyt ”iso-O” -merkkiin joten tässä on vain nopea päivitys.

Olkoon f : N → olla funktio.Joukko O ( f ) sisältää kaikki toiminnot g : N → N , joille on olemassa vakioita n ₀ ∈ N ja c ∈ N siten, että jokaiselle n ∈ N n > n ₀ kanssa on totta, että g ( n ) ≤ c f ( n ).

Nyt olemme valmiit lähestymään todellista kysymystä.

Luokka P sisältää kaikki kielet L , joille on olemassa Turingin kone D , joka päättää L ja vakio k ∈ N siten, että jokaiselle syötteelle w , D pysähtyy enintään T (| w |) -vaiheiden jälkeen toiminnolle T ∈ O ( n ↦ n ^k ).

Koska O ( n ↦ n ^k ), vaikka matemaattisesti oikein, on hankalaa kirjoittaa ja lukea, useimmat ihmiset – ollakseni rehellisiä, kaikki paitsi minä – kirjoittavat yleensä yksinkertaisesti O>(n^k ).

Huomaa, että sidonta riippuu w . Siksi argumentti, jonka teet alkukielille, on oikea vain numeroille, jotka ovat arkistokoodauksissa , missä w numero n , koodauksen pituus | w | on verrannollinen arvoon n . Kukaan ei koskaan käyttäisi tällaista koodausta käytännössä. Käyttämällä edistyneempää algoritmia kuin yksinkertaisesti kokeilemalla kaikkia mahdollisia tekijöitä, voidaan kuitenkin osoittaa, että alkulukujen kieli säilyy P : ssä, jos syötteet koodataan binaariksi (tai muuhun tukiasemaan). (Huolimatta suuresta mielenkiinnosta, tämän pystyi todistamaan vain Manindra Agrawal, Neeraj Kayal ja Nitin Saxena palkitussa lehdessä vuonna 2004, joten voit arvata, että algoritmi ei ole kovin yksinkertainen.)

triviaalit kielet {} ja Σ ^＊ ja ei-triviaali kieli { ε } ovat ilmeisesti P : ssä (minkä tahansa aakkosen kohdalla) Σ ). Voitko kirjoittaa toimintoja suosikki ohjelmointikielelläsi, jotka ottavat merkkijonon syötteeksi ja palauttavat loogisen arvon, joka kertoo, onko merkkijono sana jokaiselle näistä kielestä, ja todistaa, että funktiossasi on polynomin ajonaikainen monimutkaisuus?

Jokainen tavallinen kieli (säännöllisen lausekkeen kuvaama kieli) on kielellä P .

Olkoon Σ aakkoset ja L ⊆ Σ ^＊ . Kone V , joka ottaa koodatun sanan kahdesta sanasta w , c ∈ Σ ^＊ ja antaa 0 tai 1 lopullisen määrän vaiheiden jälkeen on todentaja kohteelle L , jos sillä on seuraavat ominaisuudet.

• Annettu ( w , c ), V tuottaa 1 vain, jos w ∈ L .
• Jokaiselle w ∈ L olemassa c ∈ Σ ^＊ siten, että V ( w , c ) = 1.

Ylläolevassa määritelmässä olevaa c -tunnusta kutsutaan todistajaksi tai todistukseksi . .

Todentaja saa antaa väärän negatiivisen vääriä todistajia varten, vaikka w todellisuudessa olisikin kohdassa L . Vääriä positiivisia tietoja ei kuitenkaan saa antaa. Lisäksi vaaditaan, että jokaiselle kielen sanalle on vähintään yksi todistaja.

Kielelle COMPOSITE, joka sisältää kaikkien ei päälukujen kokonaislukujen desimaalikoodaukset , todistaja voisi olla tekijä. Esimerkiksi (659, 709) on todistaja 467231 ∈ COMPOSITE. Voit helposti tarkistaa, että paperiarkilla ilman todistajaa todistaa, että 467231 ei ole ensisijainen, olisi vaikeaa ilman tietokonetta.

Emme sanoneet mitään siitä, miten sopiva todistaja voidaan saada Tämä on ei-deterministinen osa.

Luokka NP sisältää kaikki kielet L , joille on olemassa Turingin kone V joka vahvistaa L ja vakion k ∈ N siten, että jokaiselle tulo ( w , c ), V pysähtyy enintään T jälkeen (| | w |) vaiheet funktiolle T ∈ O ( n ↦ n^k ).

Huomaa, että yllä oleva määritelmä tarkoittaa, että jokaiselle w ∈ L on olemassa todistaja c | c | ≤ T (| w |). (Turingin kone ei pysty tarkastelemaan useampia todistajan symboleja.)

NP on P -joukko (miksi?). Ei tiedetä, onko kieliä, jotka ovat NP , mutta eivät P .

Kokonaislaskenta ei ole kieli sinänsä. Voimme kuitenkin rakentaa kielen, joka edustaa siihen liittyvää päätösongelmaa . Eli kieli, joka sisältää kaikki joukot ( n , m ) siten, että n : llä on tekijä d d ≤ m . Kutsutaan tätä kieltä FACTORiksi. Jos sinulla on algoritmi FACTORin määrittämiseen, sitä voidaan käyttää laskemaan täydellinen factoring vain polynomien yläpuolella suorittamalla rekursiivinen binäärihaku jokaiselle alkutekijälle.

On helppo osoittaa, että FACTOR on NP . Sopiva todistaja olisi yksinkertaisesti itse tekijä d , ja todentajan tarvitsee vain varmistaa, että d ≤ m ja n mod d = 0. Kaikki tämä voidaan tehdä polynomiajassa. (Muista jälleen, että koodauksen pituus laskee ja joka on logaritminen kohdassa n .)

Jos pystyt osoittamaan, että FACTOR on myös P : ssä, voit olla varma, että saat monia hienoja palkintoja. (Ja olet rikkonut merkittävän osan tämän päivän salauksesta.)

Jokaisella NP : n kielellä on karkean voiman algoritmi, joka päättää se deterministisesti. Se yksinkertaisesti suorittaa tyhjentävän haun kaikille todistajille. (Huomaa, että todistajan enimmäispituutta rajoittaa polynomi.) Joten algoritmisi, jolla päätät PRIMES, oli itse asiassa raakavoiman algoritmi päättää KOMPOSIITTI.

Viimeiseen kysymykseesi vastaamiseksi meidän on otettava käyttöön vähennys . Pienennykset ovat erittäin tehokas käsite teoreettisesta tietojenkäsittelytieteestä. Yhden ongelman pienentäminen toiseen tarkoittaa periaatteessa yhden ongelman ratkaisemista toisen ratkaisemalla ongelma.

Olkoon Σ aakkoset ja A ja B ovat kieliä Σ . A on polynomi-aika monta-yksi pelkistettävä muotoon B , jos funktio f : Σ ^＊ → Σ ^＊ seuraavilla ominaisuuksilla.

• w ∈ A   ⇔   f ( w ) ∈ B   kaikille w ∈ Σ ^＊ .
• Turingin kone voi laskea toiminnon f jokaiselle tulolle w monissa vaiheissa, joita polynomi rajoittaa | w |.

Tässä tapauksessa kirjoitamme A ≤ _p B .

olkoon A kieli, joka sisältää kaikki kaaviot (koodatut vierekkäisyysmatriiseiksi), jotka sisältävät kolmion. (Kolmio on pituussykli 3.) Olkoon edelleen B kieli, joka sisältää kaikki matriisit, joissa ei ole nollan jälkiä. (Matriisin jälki on sen tärkeimpien diagonaalielementtien summa.) Tällöin A on polynomi-aikainen moni-yksi, joka voidaan vähentää arvoon B . Tämän todistamiseksi meidän on löydettävä sopiva muunnosfunktio f . Tässä tapauksessa voimme asettaa f laskemaan vierekkäisyysmatriisin 3 ^rd -voiman. Tämä vaatii kahta matriisimatriisituotetta, joista jokaisella on polynomimutkaisuus.

On triviaalia, että L ≤ _p L . (Voitko todistaa sen muodollisesti?)

Sovellamme tätä nyt NP : ään.

Kieli L on NP -kova ja vain jos L ”≤ _p L jokaiselle kielelle L ” ∈ NP .

NP -kova kieli voi olla tai ei olla itse NP : ssä.

Kieli L on NP -complete vain ja vain, jos

• L ∈ NP ja
• L on NP -kova.

Tunnetuin NP -kokoinen kieli on SAT. Se sisältää kaikki loogiset kaavat, jotka voidaan tyydyttää. Esimerkiksi ( a ∨ b ) ∧ (¬ a ∨ ¬ b ) ∈ SAT. Kelvollinen todistaja on { a = 1, b = 0}. Kaava ( a ∨ b ) ∧ (¬ a ∨ b ) ∧ ¬ b ∉ SAT. (Kuinka todistat sen?)

Ei ole vaikea osoittaa, että SAT ∈ NP . SAT: n NP -kovuuden osoittaminen on jonkin verran työtä, mutta sen teki vuonna 1971 Stephen Cook .

Kun tämä yksi NP -kokoinen kieli oli tiedossa, oli suhteellisen helppoa näyttää muiden kielten NP -kokonaisuus pelkistämällä. Jos kielen A tiedetään olevan NP -kova, osoitetaan, että A ≤ _p B osoittaa, että B on myös NP -kova (” _p ”). Vuonna 1972 Richard Karp julkaisi luettelon 21 kielestä, jotka hän saattoi näyttää olevan NP -kokeeton SAT: n (transitiivisen) vähentämisen avulla. (Tämä on ainoa artikkeli tässä vastauksessa, jonka suosittelen sinun lukevan. Toisin kuin muut, sitä ei ole vaikea ymmärtää, ja se antaa erittäin hyvän käsityksen siitä, kuinka NP -kokonaisuuden osoittaminen pelkistyksen avulla toimii. )

Lopuksi lyhyt yhteenveto. Käytämme symboleja NPH ja NPC merkitsemään NP -kovien ja NP -kompleksien luokkia vastaavasti.

• P ⊆ NP>
• NPC ⊂ NP ja NPC ⊂ NPH , itse asiassa NPC = NP ∩ NPH määritelmän mukaan
• ( A ∈ NP ) ∧ ( B ∈ NPH )   ⇒   A ≤ _p B

Huomaa, että sisällyttäminen NPC ⊂ NP on oikea myös siinä tapauksessa, että P = NP . Jos haluat nähdä tämän, tee itsellesi selvä, että mitään ei-triviaalia kieltä ei voida vähentää triviaaliksi kieleksi ja että P : ssä on myös triviaalia kieltä ei-triviaalikielinä NP : ssä. Thi s on kuitenkin (ei kovin mielenkiintoinen) kulmatapaus.

Lisäosa

Ensisijainen sekaannuksen lähde näyttää siltä, että ajattelit ” n ”kohdassa” O ( n ↦ f ( n )) ”Algoritmin syötteen tulkintana kun se todella viittaa syötteen pituuteen . Tämä on tärkeä ero, koska se tarkoittaa, että algoritmin asymptoottinen monimutkaisuus riippuu syötteen koodauksesta .

Tällä viikolla uusi tietue suurimmalle tunnetulle Mersennen prime saavutettiin. Suurin tällä hetkellä tunnettu alkuluku on 2 ^{74   207   281} – 1. Tämä luku on niin valtava että se aiheuttaa minulle päänsärkyä, joten käytän pienempää seuraavassa esimerkissä: 2 ³¹ – 1 = 2   147   483   647. Se voidaan koodata eri tavoin.

• sen Mersennen eksponentti desimaalilukuna: 31 (2 tavua)
• desimaalilukuna: 2147483647 (10 tavua)
• unaarisena numero: 11111…11 jossa … on korvattava 2   147   483   640 lisää 1 s (melkein 2 GiB)

Kaikki nämä merkkijonot koodaavat samaa numeroa, ja kun otetaan huomioon mikä tahansa näistä, voimme helposti rakentaa minkä tahansa muun saman numeron koodauksen. (Voit korvata desimaalikoodauksen binäärillä, oktaalilla tai heksadeillä mal jos haluat. Se muuttaa pituutta vain vakiokertoimella.)

Primaalin testauksen naiivi algoritmi on polynomi vain unary-koodauksille. AKS-alkutesti on desimaalin polynomi (tai mikä tahansa muu perusta b ≥ 2 ). Lucas-Lehmer-primaatiotesti on tunnetuin algoritmi Mersennen alkukappaleille M _p p : lla pariton alkuluku, mutta se on silti eksponentiaalinen Mersennen eksponentin p (polynomi p : ssä) binäärikoodauksen pituudessa ).

Jos haluamme puhua algoritmin monimutkaisuudesta, on erittäin tärkeää, että olemme hyvin selvillä siitä, mitä esitystä käytämme. Yleisesti voidaan olettaa, että käytetään tehokkainta koodausta. Eli binääri kokonaisluvuille. (Huomaa, että kaikki alkuluvut eivät ole Mersennen alkulukuja, joten Mersennen eksponentin käyttö ei ole yleinen koodausmenetelmä.)

Teoreettisessa salauksessa monet algoritmit kulkevat muodollisesti täysin hyödytön merkkijono k 1 s ensimmäisenä parametrina. Algoritmi ei koskaan tarkastele tätä parametria, mutta sen avulla se voi muodollisesti olla polynomi muodossa k , joka on suojausparametri käytetään menettelyn turvallisuuden virittämiseen.

Joidenkin ongelmien osalta, joiden ratkaisukieli binaarikoodauksessa on NP -kokonaisuus, päätöskieli ei ole enää NP -valmis, jos upotettujen numeroiden koodaus vaihdetaan epätavalliseksi. Muiden ongelmien ratkaisukielet ovat NP -valmiit silloinkin. Jälkimmäisiä kutsutaan voimakkaasti NP -valmiiksi . Tunnetuin esimerkki on bin pakkaus .

On myös mielenkiintoista nähdä, kuinka algoritmin monimutkaisuus muuttuu, jos syöte pakataan . Esimerkiksi Mersennen alkukappaleista olemme nähneet kolme koodausta, joista kukin on logaritmisesti pakattu kuin edeltäjänsä.

Vuonna 1983 Hana Galperin ja Avi Wigderson on kirjoittanut mielenkiintoisen artikkelin yleisten kaavioalgoritmien monimutkaisuudesta, kun kaavion tulokoodaus pakataan logaritmisesti. Näiden syötteiden kohdalla kaavioiden kieli, joka sisältää kolmion ylhäältä (missä se oli selvästi P : ssä), yhtäkkiä on NP -valmis.

Ja se ”koska kielikurssit, kuten P ja NP , on määritelty kielille , ei ongelmille .

Kommentit

• Tämä vastaus ei todennäköisesti ole hyödyllinen kysyjän ymmärtämiselle. Lue muut vastaukset ja katso, mitä Nanako kamppailee. Luuletko tämän Vastaus auttaa häntä / häntä?
• Tämä vastaus ei välttämättä auta OP: ta, mutta auttaa varmasti muita lukijoita (mukaan lukien minä).
• erittäin hyödyllinen vastaus! harkitse matemaattisten symbolien korjaamista väärin näytetään.

Yritän antaa sinulle vähemmän epämuodollisen määritelmän samalle.

P-ongelmat: ongelmat, jotka voidaan ratkaista polynomiajassa. Sisältää ongelmia, jotka voidaan ratkaista tehokkaasti.

NP-ongelma: ongelmat, jotka voidaan vahvistaa polynossa mialla. Esimerkiksi: Matkustava myyjä, piirisuunnittelu. NP-ongelmat ovat eräänlaisia palapelejä (kuten sudoku). Annettuna oikea ratkaisu ongelmaan voimme tarkistaa ratkaisumme hyvin nopeasti, mutta jos yritämme todella ratkaista sen, se voi kestää vain ikuisesti.

Nyt P vs NP todella kysyy, voiko ongelma, jonka ratkaisu voidaan ratkaista nopeasti tarkistetaan olevan oikein, onko sitten aina nopea tapa ratkaista se. Kirjoitetaan siis matemaattisesti: onko NP P: n osajoukko vai ei?

Palatakseni nyt NP: hen on täydellinen: nämä ovat NP-ongelmien todella vaikeita ongelmia. Siksi, jos on olemassa nopeampi tapa ratkaista NP-täydellinen, NP-täydellisestä tulee P ja NP-ongelmat romahtavat P: ksi. Esimerkiksi shakin parhaan siirron valitseminen on yksi niistä.

Jos jotain jää epäselväksi, yritä katsoa tämä video: https://www.youtube.com/watch?v=YX40hbAHx3s

Toivon, että tämä antaa epäselvän muodon.