EXPSPACE

Edellisen lauseen todistus suoritetaan kahdessa vaiheessa. Meidän on ensin todistettava EXPSPACEn jäsenyys ja osoitettava sitten, että tämä kieli on EXPSPACE-vaikea (toisin sanoen mikä tahansa EXPSPACE-kieli supistuu polynomiajassa ). ATLLREX↑{\ displaystyle ALL_ {REX \ ylöspäin}}ATLLREX↑{\ displaystyle ALL_ {REX \ ylöspäin}}

ATLLREX↑∈{\ displaystyle KAIKKI_ {REX \ ylöspäin} \ sisään}

REX- koon perusteella seuraava algoritmi antaa mahdollisuuden määrittää eksponentiaalisessa tilassa, jos  : e{\ displaystyle e}ei{\ displaystyle n}L(e)=AT⋆{\ displaystyle L (e) = A ^ {\ tähti}}

1. Korvaa eksponentointitoiminnot ketjutuksella. Saamme koon kaavan .EI=2O(ei){\ displaystyle N = 2 ^ {O (n)}}
2. Muunna tämä kaava (naiivisti) ei-deterministiseksi automaatiksi. Tämä toiminto vaatii tilaa .O(EI){\ displaystyle O (N)}
3. Määritä edellinen automaatti. Uudessa ohjaimessa voi olla korkeintaan tiloja.2O(EI)=22O(ei){\ displaystyle 2 ^ {O (N)} = 2 ^ {2 ^ {O (n)}}}
4. e{\ displaystyle e}kuuluu vain ja vain, jos mitään edeltävää tilaa ei voida saavuttaa edellisessä deterministisessä automaatissa. Savitchin lauseen mukaan tämä pitää paikkansa koon kuvaajassa .ATLLREX↑{\ displaystyle ALL_ {REX \ ylöspäin}}O(EI2){\ displaystyle O (N ^ {2})}2O(EI){\ displaystyle 2 ^ {O (N)}}

Koska tilaa ei ole mahdollista käyttää , determinististä automaattia ei rakenneta yllä olevassa vaiheessa 3. Sen sijaan se lasketaan uudelleen vaiheen 4 läpi. 2O(EI)=22O(ei){\ displaystyle 2 ^ {O (N)} = 2 ^ {2 ^ {O (n)}}}

ATLLREX↑{\ displaystyle ALL_ {REX \ ylöspäin}}

Tarkastellaan deterministisen Turingin koneen avaruudessa tunnistamaa kieltä . Yhdistämme REX kuten . Tarkemmin sanottuna meillä on . L{\ displaystyle {\ mathcal {L}}} M=(Q,Γ,B,Σ,q0,5,F){\ displaystyle M = (Q, \ Gamma, B, \ Sigma, q_ {0}, \ delta, F)}2eik{\ displaystyle 2 ^ {n ^ {k}}}w{\ displaystyle w}wR{\ displaystyle w_ {R}}w∈L⇔L(wR)∈ATLLREX↑{\ displaystyle w \ sisään {\ mathcal {L}} \ Vasen suora L (w_ {R}) \ ALL_ {REX \ ylöspäin}}L(wR)={s:s on sana, joka ei edusta laskua hylkäävää M varma w}{\ displaystyle L (w_ {R}) = \ {s: s {\ text {on sana, joka ei kuvaa}} M {\ text {on}} w \}} hylkäävää laskutoimitusta

Tilan koneen aikaan sen suorittamisen edustaa sana , jossa on sisältöä nauha laatikko , valtion koneen ja symbolin asetetaan lukupää. Koska se suoritetaan avaruudessa , voidaan olettaa, että se on kokoa (vaikka se merkitsisikin täydentämistä valkoisilla symboleilla ). M{\ displaystyle M}r{\ displaystyle r}VSr=x1x2⋯xiqxi+1⋯{\ displaystyle C_ {r} = x_ {1} x_ {2} \ cdots x_ {i} qx_ {i + 1} \ cdots}xj{\ displaystyle x_ {j}}j{\ displaystyle j}q{\ displaystyle q}xi+1{\ displaystyle x_ {i + 1}}M{\ displaystyle M}2eik{\ displaystyle 2 ^ {n ^ {k}}}VS{\ displaystyle C}2eik{\ displaystyle 2 ^ {n ^ {k}}}B{\ displaystyle B}

Tulon laskenta esitetään sitten sanalla, jossa kukin on koneen tilan koodaus sen suorituksen aikana. M{\ displaystyle M}w{\ displaystyle w}VS1#VS2#...#VSt{\ displaystyle C_ {1} \ # C_ {2} \ # \ dots \ #C_ {t}}VSi{\ displaystyle C_ {i}}i{\ displaystyle i}

Laskelma on yhtä merkintää ei torju, jos se täyttää vähintään yhden 3 seuraavat ehdot: wVS=VS1#VS2#...#VSt{\ displaystyle w_ {C} = C_ {1} \ # C_ {2} \ # \ pistettä \ #C_ {t}}M{\ displaystyle M}w{\ displaystyle w}

1. VS1{\ displaystyle C_ {1}}ei ole mahdollinen .M{\ displaystyle M}
2. on 2 peräkkäistä kokoonpanoa, jotka edustavat mahdotonta siirtymistä.VSi,VSi+1{\ displaystyle C_ {i}, C_ {i + 1}}
3. VSt{\ displaystyle C_ {t}} ei ole lopullinen hylkäävä kokoonpano.

Kuhunkin näistä kolmesta ehdosta rakennamme järkevän lausekkeen, joka tuottaa ehdon täyttävän sanaryhmän (merkitsemme ja ). e{\ displaystyle e}Δ=Γ∪Q∪{#}{\ displaystyle \ Delta = \ Gamma \ cup Q \ cup \ {\ # \}}Δ-klo=Δ∖{klo}{\ displaystyle \ Delta _ {- a} = \ Delta \ taaksepäin vinoviiva {{a \}}

Ehto 1. Aluksi kone on tilassa ja kirjoitettu nauhalleen. Näin ollen, ainoa mahdollinen ensimmäinen kokoonpano on: . Seuraava säännöllinen lauseke tuottaa sitten joukon sanoja, jotka täyttävät ehdon 1: M{\ displaystyle M}q0{\ displaystyle q_ {0}}w{\ displaystyle w}q0w1⋯weiB⋯B{\ displaystyle q_ {0} w_ {1} \ cdots w_ {n} B \ cdots B}Rbklod-stklort=Δ-q0Δ⋆+Δ1Δ-w1Δ⋆+Δ2Δ-w2Δ⋆+⋯+Δei+1(Δ+e)2eik-ei-2Δ-BΔ⋆+Δ2eikΔ-#Δ⋆{\ displaystyle R_ {bad-start} = \ Delta _ {- q_ {0}} \ Delta ^ {\ star} + \ Delta ^ {1} \ Delta _ {- w_ {1}} \ Delta ^ {\ tähti } + \ Delta ^ {2} \ Delta _ {- w_ {2}} \ Delta ^ {\ star} + \ cdots + \ Delta ^ {n + 1} (\ Delta + \ varepsilon) ^ {2 ^ {n ^ {k}} - n-2} \ Delta _ {- B} \ Delta ^ {\ star} + \ Delta ^ {2 ^ {n ^ {k}}} \ Delta _ {- \ #} \ Delta ^ {\ tähti}}

Ehto 2. Jos haluat tietää, onko siirtymä kelvollinen vai ei, riittää, että tutkitaan kutakin peräkkäisten kokoonpanoikkunoiden paria, joiden koko on 3 ja jotka on keskitetty nykyiseen tilaan (esimerkiksi kokoonpanolle, jossa ikkuna on ). Konfiguraation muiden kirjainten ei pidä kehittyä vain yhden laskentavaiheen jälkeen. Ja kaksi ikkunaa ja se on huomattava siitä, ei voi olla kahta peräkkäistä kokoonpanot, joilla on vastaavasti ja ikkunoihin. Se generoi sitten joukko sanoja tarkistaa 2 toimitetaan käyttäen seuraavaa säännöllinen lauseke: . VS=x1x2⋯xiqxi+1⋯{\ displaystyle C = x_ {1} x_ {2} \ cdots x_ {i} qx_ {i + 1} \ cdots}xiqxi+1{\ displaystyle x_ {i} qx_ {i + 1}}klobvs.{\ displaystyle abc}def{\ displaystyle def}bklod(klobvs.,def){\ displaystyle huono (abc, def)}klobvs.{\ displaystyle abc}def{\ displaystyle def}Rbklod-wieidow=⋃bklod(klobvs.,def)Δ⋆klobvs.Δ2eik-2defΔ⋆{\ displaystyle R_ {bad-window} = \ bigcup _ {bad (abc, def)} \ Delta ^ {\ star} abc \ Delta ^ {2 ^ {n ^ {k}} - 2} def \ Delta ^ { \ tähti}}

Ehto 3. Oletetaan, että kone päättyy tilassa , jos laskenta hylätään. Siten, jotta se ei ole hylkäävä lopullinen kokoonpano, riittää, että se ei sisällä . Seuraava säännöllinen lauseke ja tuottaa joukon sanoja, jotka täyttävät ehdon 3 . M{\ displaystyle M}qrejevs.t{\ displaystyle q_ {hylkää}}VSt{\ displaystyle C_ {t}}wVS{\ displaystyle w_ {C}}qrejevs.t{\ displaystyle q_ {hylkää}}Rbklod-rejevs.t=Δ-qrejevs.t⋆{\ displaystyle R_ {bad-reject} = \ Delta _ {- q_ {reject}} ^ {\ star}}

Lopuksi huomaamme . Meillä on hyvää ja niin . Lisäksi se rakentuu hyvin polynomiajassa ( on kooltaan ). wR=Rbklod-stklort+Rbklod-wieidow+Rbklod-rejevs.t{\ displaystyle w_ {R} = R_ {huono alku} + R_ {huono ikkuna} + R_ {huono-hylkää}}L(wR)={s:s on sana, joka ei edusta laskua hylkäävää M varma w}{\ displaystyle L (w_ {R}) = \ {s: s {\ text {on sana, joka ei kuvaa}} M {\ text {on}} w \}} hylkäävää laskutoimitustaw∈L⇔L(wR)∈ATLLREX↑{\ displaystyle w \ sisään {\ mathcal {L}} \ Vasen suora L (w_ {R}) \ ALL_ {REX \ ylöspäin}}wR{\ displaystyle w_ {R}}ei=|w|{\ displaystyle n = | w |}wR{\ displaystyle w_ {R}}O(eik){\ displaystyle O (n ^ {k})}

Logiikassa

Joidenkin lineaarisen ajallisen logiikan fragmenttien tyydyttävyysongelma ensimmäisen asteen kvantifikaatioilla on EXPSPACE-täydellinen.

Bibliografia

• (en) Sanjeev Arora ja Boaz Barak , laskennallinen monimutkaisuus: moderni lähestymistapa , Cambridge University Press ,2009( ISBN  0-521-42426-7 )
• Sylvain Perifel , algoritminen monimutkaisuus , ellipsit ,2014, 432  Sivumäärä ( ISBN  9782729886929 , lue verkossa )

Ulkoiset linkit

• (en) EXPSPACE-luokka monimutkaisuuden eläintarhassa

Huomautuksia ja viitteitä

1. (in) Chris Umans Kevin Lee, "  laskennallinen kompleksisuus, Lecture Notes 8  " ,19. helmikuuta 2010
2. Albert R. Meyer ja Larry Stockmeyer . Neliön muotoisten säännöllisten lausekkeiden ekvivalenssiongelma vaatii eksponentiaalista tilaa . IEEE: n 13. kytkentä- ja automaatioteoria-symposium , lokakuu 1972, s. 125–129.
3. I. Hodkinson , R. Kontchakov , A. Kurucz ja F. Wolter , "  Ensimmäisen asteen lineaarisen ajallisen logiikan päätettävien fragmenttien laskennallisesta monimutkaisuudesta  ", 10. kansainvälinen symposium on Temporal Representation and Reasoning, 2003 ja neljäs kansainvälinen ajallinen konferenssi. Logiikka. Menettely ,1. st heinäkuu 2003, s.  91–98 ( DOI  10.1109 / TIME.2003.1214884 , luettu verkossa , käytetty 17. lokakuuta 2016 )