Kuvaava monimutkaisuus

In tietojenkäsittelyteoria , kuvaileva monimutkaisuus on haara monimutkaisuus teoria ja malli teoria , joka luonnehtii monimutkaisuus luokkien osalta logiikan kuvaamiseen ongelmia.

Kuvaava monimutkaisuus antaa uuden näkökulman, koska määrittelemme monimutkaisuusluokitukset turvautumatta koneiden käsitteeseen, kuten Turingin koneisiin . Esimerkiksi luokka NP vastaa eksistentiaalisen toisen asteen logiikassa ilmaistavaa joukkoa ongelmia : se on Faginin lause .

Periaate

Esimerkki: kuvaajan väritys

Selitetään kuvailevan monimutkaisuuden periaate graafin 3-värin ongelmalla . Se on noin päätöksestä ongelmasta , joka koostuu tietää, koska kuvaaja, jos voi värjätä sen kärkipisteet kanssa kolme väriä niin, että kahden vierekkäisen vertices eivät ole samaa väriä. Oikealla olevassa kuvassa on esimerkki kolmivärisestä kaaviosta.

Kolmivärjäysongelma on NP-luokassa . Värin perusteella on helppo tarkistaa (ts. Polynomiajassa kaavion koossa), että kaksi vierekkäistä kärkeä eivät ole samaa väriä.
Toisaalta 3-väritysongelma kuvataan seuraavan eksistentiaalisen toisen asteen logiikan kaavalla . Tämä kaava lukee "on yksi joukko pisteitä C 1 , toinen joukko pisteitä C 2 , toinen joukko pisteitä C 3 (1, 2, 3 ovat kolme mahdollista väriä), kuten: ∃VS1,∃VS2,∃VS3,(∀s,⋁i=13VSi(s))∧(∀s⋀i,j=1i≠j3(¬VSi(s)∨¬VSj(s)))∧(∀t,R(s,t)→⋀i=13(¬VSi(s)∨¬VSi(t))){\ displaystyle \ olemassa C_ {1}, \ olemassa C_ {2}, \ olemassa C_ {3}, \ vasen (\ kaikki s, \ bigvee _ {i = 1} ^ {3} C_ {i} (s) \ oikea) \ maa \ vasen (\ kaikki s \ bigwedge _ {i, j = 1i \ neq j} ^ {3} (\ ei C_ {i} (s) \ lor \ ei C_ {j} (s)) \ oikea) \ maa \ vasen (\ kaikki t, R (s, t) \ oikeanpuoleinen \ isowedge _ {i = 1} ^ {3} (\ ei C_ {i} (s) \ lor \ ei ole C_ {i} (t)) \ oikea)} ${\ displaystyle \ olemassa C_ {1}, \ olemassa C_ {2}, \ olemassa C_ {3}, \ vasen (\ kaikki s, \ bigvee _ {i = 1} ^ {3} C_ {i} (s) \ oikea) \ maa \ vasen (\ kaikki s \ bigwedge _ {i, j = 1i \ neq j} ^ {3} (\ ei C_ {i} (s) \ lor \ ei C_ {j} (s)) \ oikea) \ maa \ vasen (\ kaikki t, R (s, t) \ oikeanpuoleinen \ isowedge _ {i = 1} ^ {3} (\ ei C_ {i} (s) \ lor \ ei ole C_ {i} (t)) \ oikea)}$
- mikä tahansa kärki on värillinen (mikä tahansa kärki on jossakin osajoukossa C i ),
- millä tahansa kärjellä on korkeintaan vain yksi väri (mikä tahansa kärki on korkeintaan yhdessä osajoukossa C i ),
- kaksi vierekkäistä kärkeä ovat eri värejä.

Päätösongelma kyselynä

Siten kuvailevassa monimutkaisuudessa päätösongelma kuvataan loogisella kaavalla, joka vastaa kyselyn tekemistä (esimerkiksi kysely "onko kaavio 3 väritettävissä?"). Instanssi päätöksen ongelma on malli (esim kuvaaja 3-väritys ongelma nähdään malli), jonka looginen kaavat voidaan arvioida. Päätösongelman positiiviset esiintymät (eli esimerkissä 3 väritettävät kaaviot) ovat täsmälleen mallit, joissa kaava on totta.

Toinen esimerkki

Tarkastellaan päätösongelmaa A, joka koostuu sen määrittämisestä, onko graafi G sellainen, että mikä tahansa G: n kärki sallii tulevan reunan. Kuvaaja G nähdään mallina, jossa toimialueen elementit ovat kaavion kärjet ja kaavion suhde on predikaatti . Päätösongelma A voidaan ilmaista ensimmäisen asteen logiikassa, koska positiiviset instanssit kuvataan kaavalla (mikä tahansa kärkipiste s myöntää seuraajan t). $R$ ${\ displaystyle \ kaikki s, \ olemassa t, sRt}$

Faginin lause

Verkkotunnuksen ensimmäinen tulos ja yksi tärkeimmistä on Faginin lause, joka antaa vastaavuuden:

NP määritelmän, luokka päätöksen ongelmia, joihin on helppo tarkistaa ratkaisun;
ja eksistentiaalisessa toisen asteen logiikassa ilmaistava ongelmaluokka eli toisen asteen logiikka , jossa estetään predikaattien ja funktioiden yleinen kvantisointi.

Luokkien ja logiikkojen välinen vastaavuus

Monet muut luokat on myös karakterisoitu samalla tavalla, ja ne on tiivistetty seuraavaan taulukkoon, enimmäkseen Neil Immerman .

Monimutkaisuusluokat	Vastaava logiikka
AC⁰	ensiluokkainen logiikka
NL	ensiluokkainen logiikka transitiivisella sulkemisella
P	ensimmäisen asteen logiikka pienimmällä kiinteällä pisteellä
NP	eksistentiaalinen toisen asteen logiikka
co-NP	yleinen toisen asteen logiikka
PH	toisen asteen logiikka
PSPACE	toisen asteen logiikka transitiivisella sulkimella
EXPTIME	toisen asteen logiikka pienimmällä kiinteällä pisteellä
PERUS	korkeamman asteen logiikka
RE	eksistentiaalinen ensimmäisen asteen logiikka kokonaisluvuille
ydin	yleinen ensimmäisen asteen logiikka kokonaislukuihin nähden

Esimerkki NL: stä

Kiinnostuksen kohteet

Neil Immerman perustelee kuvailevan monimutkaisuuden teoriaa, koska se osoittaa, että Turingin koneilla määritellyt monimutkaisuusluokat ovat luonnollisia : ne ovat määriteltäviä, vaikka emme käyttäisikään klassisia laskennallisia malleja. Lisäksi tämä teoria antaa uuden näkökulman tiettyihin tuloksiin ja tiettyihin monimutkaisuusteorian oletuksiin, esimerkiksi Abiteboulin ja Vianun lause (en) osoittavat, että luokat P ja PSPACE ovat samat, jos logiikan inflaatiokorjauspiste (IFP) ja osittainen Kiinteä piste (PFP) on yhtä suuri.

Ulkoinen linkki

Neil Immermanin kuvaava monimutkaisuus, kaavio .

Vaihtoehdot

Luokka PTIME, joka on leikattu invarianttien ongelmien kanssa bisimulaatiolla, vastaa korkeamman ulottuvuuden mu-laskennan logiikkaa .

Bibliografia

Artikkelit

(en) Ronald Fagin , ” Yleistetyt ensiluokkaiset spektrit ja polynomi-aikatunnistettavat sarjat ” , Proc. SIAM-AMS Sympos. Appl. Matematiikka. , Amer. Matematiikka. Soc., Voi. VII "Laskennan monimutkaisuus" ,1974, s. 43-73 ( matemaattiset arvostelut 0371622 , luettu verkossa , käytetty 7. marraskuuta 2019 )
(en) Neil Immerman , " Kielet, jotka vangitsevat monimutkaisuusluokkia " , STOC '83 Proceedings of the 15th ACM symposium on Theory of computing ,1983, s. 347-354 ( ISBN 0-89791-099-0 , DOI 10.1145 / 800061.808765 , lue verkossa )
(en) Serge Abiteboul et Victor Vianu , " Generic Computation and its Complexity " , STOC '91 Proceedings of the Third-Year ACM symposium on Theory of Computing ,1991, s. 209-219 ( ISBN 0-89791-397-3 , DOI 10.1145 / 103418.103444 )

Toimii

(en) Neil Immerman , kuvaava monimutkaisuus , New York, Springer-Verlag,1999( ISBN 0-387-98600-6 , online-esitys )
(en) Martin Grohe , kuvaava monimutkaisuus, kanonisointi ja määriteltävä kaavion rakenneteoria , Cambridge University Press,2017, 554 Sivumäärä ( ISBN 978-1-139-02886-8 , lue verkossa ) , luku . I.3 ("Kuvaava monimutkaisuus") , s. 40-93

Huomautuksia ja viitteitä

( Fagin 1974 ).
Lähteet tärkeydelle: Olemme nyt valmiita ilmaisemaan Faginin lauseen ja Immerman-Vardi-lauseen, jotka ovat epäilemättä kaksi perustavanlaatuista tulosta kuvailevassa monimutkaisuusteoriassa. vuonna ( Grohe 2017 )
Katso ( Immerman 1983 ) johdanto .
( Abiteboul ja Vianu 1991 ).
Martin Otto , " Bisimulation-invariant PTIME and higher-dimensional μ-calculus ", teoreettinen tietojenkäsittely , voi. 224, n ° 1,6. elokuuta 1999, s. 237–265 ( ISSN 0304-3975 , DOI 10.1016 / S0304-3975 (98) 00314-4 , luettu verkossa , käytetty 22. marraskuuta 2019 )