NP täydellinen ongelma

NP-täydellinen ongelma - algoritmien teoriassa ongelma, jonka vastaus on "kyllä" tai "ei" luokasta NP , johon mikä tahansa muu tämän luokan ongelma voidaan pelkistää polynomiajassa (eli käyttämällä operaatioita, joiden numero ei ylitä jotakin polynomia alkuperäisen tiedon koosta riippuen). Siten NP-täydelliset ongelmat muodostavat tietyssä mielessä "tyypillisten" NP-luokan ongelmien osajoukon: jos joillekin niistä löydetään "polynomiaalisesti nopea" ratkaisualgoritmi, niin mikä tahansa muu NP-luokan ongelma voidaan ratkaista. yhtä "nopeasti"".

Muodollinen määritelmä

Aakkoset ovat mikä tahansa rajallinen merkkijoukko ( esimerkiksi {} tai {}). Kaikkien mahdollisten sanojen joukko ( tämän aakkosten merkeistä koostuvaviimeinen merkkijono ) joidenkin aakkosten kohdalla on merkitty. Kieli aakkosten ylion mikä tahansajoukon osajoukko , ts. ${0,1}$ ${a,b,c}$ $\Sigma$ $\Sigma ^{*}$ $L$ $\Sigma$ $\Sigma ^{*}$ $L\alajoukko \Sigma ^{*}$

Kielen tunnistamisen tehtävänä on määrittää, kuuluuko tietty sana kieleen . $L$ $L$

Olkoon ja olla kaksi kieltä aakkosten päällä . Kielen sanotaan olevan pelkistävissä (Karpin mukaan) kieleksi , jos on olemassa funktio , , joka on laskettavissa polynomiajassa ja jolla on seuraava ominaisuus: $L_{1}$ $L_{2}$ $\Sigma$ $L_{1}$ $L_{2}$ $f\colon \Sigma ^{*}\to \Sigma ^{*}$

$x\in L_{1}$ jos ja vain jos . Karpin pelkistyvyys on merkitty tai . $f(x)\in L_{2}$ $L_{1}{\leq }_{p}L_{2}$ $L_{1}\varpropto L_{2}$

Kielen sanotaan olevan NP-kova , jos mikä tahansa luokan NP kieli on pelkistävissä siihen. Kielen sanotaan olevan NP-täydellinen , jos se on NP-kova ja kuuluu itse luokkaan NP. $L_{2}$

Epävirallisesti sanottuna se, että ongelma pelkistetään ongelmaksi , tarkoittaa, että ongelma "ei ole vaikeampi" kuin ongelma (koska jos voimme ratkaista , voimme ratkaista ja ). Siten NP-kovien ongelmien luokka sisältää NP-täydelliset ongelmat ja ongelmat, jotka ovat niitä "kovempia" (eli ne ongelmat, joihin NP-täydelliset ongelmat voidaan vähentää). NP-luokkaan kuuluvat NP-täydelliset ongelmat ja niitä "helppoisemmat" ongelmat (eli ne ongelmat, jotka on pelkistetty NP-täydellisiksi ongelmiksi). $A$ $B$ $A$ $B$ $B$ $A$

Määritelmästä seuraa, että jos löydetään algoritmi, joka ratkaisee jonkin (mikä tahansa) NP-täydellisen ongelman polynomiajassa, niin kaikki NP-ongelmat ovat luokkaa P , eli ne ratkaistaan polynomiajassa.

NP-täydellinen vahvassa merkityksessä

Tehtävää kutsutaan NP-täydelliseksi vahvassa merkityksessä, jos siinä on alitehtävä, joka:

ei ole ongelma numeeristen parametrien kanssa (eli tässä tehtävässä havaittujen suureiden maksimiarvoa rajoittaa ylhäältä syötteen pituuden polynomi)
on NP-täydellinen.

Tällaisten ongelmien luokkaa kutsutaan NPCS :ksi . Jos hypoteesi P ≠ NP on totta, NPCS-ongelmalle ei ole pseudopolynomiaalista algoritmia .

Hypoteesi P ≠ NP

Kysymys luokkien P ja NP yhteensattumisesta on ollut yksi keskeisistä avoimista ongelmista yli kolmenkymmenen vuoden ajan . Tiedeyhteisöllä on taipumus antaa kielteinen vastaus tähän kysymykseen [1] – tässä tapauksessa NP-täydellisiä ongelmia ei voida ratkaista polynomiajassa.

Esimerkkejä NP-täydellisistä ongelmista

Katso myös

Luokkien P ja NP yhtäläisyys

Muistiinpanot

↑ William I. Gasarch. P=?NP-kysely. (neopr.) // SIGACT News. - 2002. - T. 33 , nro 2 . - S. 34-47 . - doi : 10.1145/1052796.1052804 .
↑ Erik D. Demaine, Susan Hohenberger, David Liben-Nowell. Tetris on kova, jopa likimääräinen . Tulosta.

Kirjallisuus

Gary M., Johnson D. Tietojenkäsittelykoneet ja kovat ongelmat Arkistoitu 4. marraskuuta 2019 Wayback Machinessa . M.: Mir, 1982.
Thomas H. Kormen ym. Luku 34. NP-Completeness // Algoritmit: rakentaminen ja analyysi = Introduction to Algorithms. - 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 .

Linkit

NP täydellisyys
Pelien ja palapelien laskennallinen monimutkaisuus arkistoitu 6. joulukuuta 2006 Wayback Machinessa
Kokoelma NP-optimointiongelmista. Toimittajat - Pierluigi Crescenzi, Viggo Kann Arkistoitu 5. joulukuuta 2006 Wayback Machinessa

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

NP-täydellisiä ongelmia
Pinoamisen (pakkauksen) maksimointiongelma	Pakkaus säiliöihin kaksiulotteinen pakkaus lineaarinen pakkaus pakkaus painon mukaan pakkaus arvon mukaan Reppu ongelma
graafiteorian joukkoteoria	Vertex-kannen ongelma Napsauta ongelma Itsenäisen joukon (joukon) ongelma Aseta peittoongelma Steinerin ongelma Matkamyyjän ongelma Yleinen matkamyyjän ongelma
Algoritmiset ongelmat	Boolen kaavojen tyydyttävyysongelma (konjunktiivisessa normaalimuodossa)
Logiikkapelejä ja pulmia	Yleiset tunnisteet (peli N 2 -1:ssä) lyhin ratkaisu ongelma Ongelmat, joiden ratkaisuja käytetään Tetrisissä Yleistynyt Sudoku-ongelma Latinalaisen neliön täyttöongelma Kakuron tehtävä
Vaikeusluokat Toimintatutkimus Optimointi Kombinatorinen optimointi Sovellettu matematiikka Algoritmien teoria Dynaaminen ohjelmointi 21 NP-täydellinen Karp-ongelma