Polynomipelkistys
Polynomi vähentäminen on työkalu tietojenkäsittelyteoria , tarkemmin sanottuna kompleksisuusteoriaan . Se on erityinen luokka erityisen tärkeitä vähennyksiä , erityisesti ongelman P = NP suhteen .
Määritelmä
Osana virallista kieltä varten päätöksen ongelmia , sanomme, että kieli on pienennettävissä polynomiaikainen että kieli (merkitty ) jos on olemassa computable funktio polynomiajassa sellainen, että kaikkien , jos ja vain jos . Kutsumme toiminto pienennystoimintoa ja polynomialgoritmin joka laskee kutsutaan vähentäminen algoritmi .
L1{\ displaystyle L_ {1} \!}L2{\ displaystyle L_ {2} \!}L1≤PL2{\ displaystyle L_ {1} \ leq _ {P} L_ {2}} f:{0,1}∗→{0,1}∗{\ displaystyle f: \ left \ {0,1 \ right \} ^ {*} \ rightarrow \ left \ {0,1 \ right \} ^ {*}}x∈{0,1}∗{\ displaystyle x \ sisään \ vasen \ {0,1 \ oikea \} ^ {*}}x∈L1{\ displaystyle x \ sisään L_ {1}}f(x)∈L2{\ displaystyle f (x) \ muodossa L_ {2}}f{\ displaystyle f \!}f{\ displaystyle f \!}
Suhde päätösongelman ja siihen liittyvän kielen välillä
Koodaus
Joko päätösongelma . Tämän ongelman esiintymät ovat abstrakteja esineitä siinä mielessä, että niiden määritelmä on puhtaasti matemaattinen. Jotta tämä ongelma voidaan toteuttaa, ne on kuitenkin edustettava ohjelman ymmärrettävässä muodossa. Tässä tulee käsite koodauksesta . Me määrittelemme koodaus funktiona päätöksen ongelma , koska ollessa injektiivinen sovellus , joka assosioituu joukko abstrakteja tapauksia elementti . Siten kun ohjelmoija koodaa ongelman, ongelman esiintymiä edustavat muuttujat käännetään ( kääntäjä staattisten kielten tapauksessa, tulkki dynaamisten kielten tapauksessa) binäärikieleksi. Koodaus on siis tapa siirtyä abstraktista ongelmasta konkreettiseen ongelmaan. Itse asiassa, jos ratkaisu päätös ongelma abstrakti esimerkiksi on kun oikeusasteen liuos betonin ongelma on . On kuitenkin pieni ongelma: on mahdollista, että elementit eivät vastaa ongelmaa (eli niillä ei ole ennakkotapaus ). Mukavuuden vuoksi oletetaan, että mikä tahansa tällainen ketju on kuva 0.
Q{\ displaystyle Q \!}vs.{\ displaystyle c \!}Q{\ displaystyle Q \!}Q{\ displaystyle Q \!}{0,1}∗{\ displaystyle \ vasen \ {0,1 \ oikea \} ^ {*}}i∈Minä{\ displaystyle i \ sisään I}Q(i)∈{0,1}{\ displaystyle Q (i) \ vasemmalla \ {0,1 \ oikea \}}vs.(i)∈{0,1}∗{\ displaystyle c (i) \ vasemmalla \ {0,1 \ oikea \} ^ {*}}Q(i){\ displaystyle Q (i) \!}{0,1}∗{\ displaystyle \ vasen \ {0,1 \ oikea \} ^ {*}}
Suhde päätösongelmien ja niitä ratkaisevien algoritmien välillä
- Algoritmi hyväksyy merkkijonon, jos syötteen saatuaan algoritmi poistuuAT{\ displaystyle A \!} x∈{0,1}∗{\ displaystyle x \ sisään \ vasen \ {0,1 \ oikea \} ^ {*}}x{\ displaystyle x \!}AT(x)=1{\ displaystyle A (x) = 1 \!}
- Algoritmi hylkää merkkijonon, jos .AT{\ displaystyle A \!} x{\ displaystyle x \!}AT(x)=0{\ displaystyle A (x) = 0 \!}
Kieli hyväksytään
- Algoritmin hyväksymä kieli on algoritmin hyväksymä merkkijono, eli .AT{\ displaystyle A \!}L={x∈{0,1}∗:AT(x)=1}{\ displaystyle L = \ left \ {x \ in \ left \ {0,1 \ right \} ^ {*}: A (x) = 1 \ right \}}
Kieli päätetty
- Kieli on päätetty algoritmin , jos jokin bittijono kuulumattomat hylkää .L{\ displaystyle L \!}AT{\ displaystyle A \!}L{\ displaystyle L \!}AT{\ displaystyle A \!}
Monimutkaisuusluokka ja kieli
Voimme epämuodollisesti määritellä monimutkaisuusluokan joukoksi kieliä, joiden jäsenyys määritetään mittaamalla algoritmin monimutkaisuus , joka määrittää, kuuluuko tietty merkkijono kielelle . Siten monimutkaisuusluokka voidaan määritellä joukoksi kieliä, joille polynomi-aika-algoritmi päättää.
x{\ displaystyle x \!}L{\ displaystyle L \!}P{\ displaystyle P \!}{0,1}∗{\ displaystyle \ vasen \ {0,1 \ oikea \} ^ {*}}
Apuohjelma
Käsitettä polynomiajan vähenemisestä käytetään algoritmien monimutkaisuuden teorian puitteissa ongelmien luokittelun mahdollistamiseksi. Se todellakin antaa mahdollisuuden osoittaa muodollisella tavalla ja polynomiajassa, että ongelma on ainakin yhtä vaikea kuin toinen: jos silloin se ei ole vaikeampi kuin tai sanotaan teoreettisemmalla tavalla: ja että sinulla on sama luokka monimutkaisuus.
L1≤PL2{\ displaystyle L_ {1} \ leq _ {P} L_ {2}}L1{\ displaystyle L_ {1} \!}L2{\ displaystyle L_ {2} \!}L1{\ displaystyle L_ {1} \!}L2{\ displaystyle L_ {2} \!}
Esimerkkejä pelkistyksestä
- Katettu osajoukkosummalla
- Napsauta 3-SAT
- SAT - 3-SAT
- Alajoukko SAT: ksi
- 3-SAT napsauttamalla
- 3-SAT kärjessä
Huomautuksia ja viitteitä
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">