Immerman-Szelepcsényi tétel

A Immerman-Szelepcsényi tétel egy tétel az elméleti számítógép-tudomány és különösen a elméletének összetettsége bizonyította 1987-ben önállóan Neil Immerman és Róbert Szelepcsényi , és amely elnyerte azokat együttesen a Gödel-díjat 1995-ben egy egyszerűsített változata ennek a tételnek jelentése NL = ko-NL .

Bevezetés

A tétel a nem determinisztikus Turing-gépekkel végzett számítások térbeli összetettségére vonatkozik . A térbeli bonyolultságot a szalagon lévő cellák számával mérjük, amelyet a Turing-gép számításai foglalnak el. A bejegyzés nagysága szerint fejezzük ki.

A nem determinisztikus gépek esetében mindig kissé trükkös a komplexitásról beszélni, mivel adott esetben több, sőt végtelen számítás is létezhet. Először is csak a számításokat vesszük figyelembe. E számítások közül pedig az, amelyik a legkedvezőbb az elvégzett mérés szempontjából, vagy a leggyorsabb az idő bonyolultsága szempontjából , vagy a leggazdaságosabb a hely komplexitása szempontjából . Végül, azokban a problémákban, amelyek „igen-nem” válaszokkal rendelkeznek, ami jelen esetben van, csak sikeres számításokat veszünk figyelembe, amelyek ezért pozitív választ adnak.

Az NSPACE jelöli azokat a problémákat, amelyeket ily módon egy nem determinisztikus Turing-géppel lehet megoldani, legfeljebb az adatok méretének függvényében , és az NSPACE-vel együtt a problémákat, beleértve azokat a kiegészítőket is, amelyek képesek legfeljebb a helyén lévő nemdeterminisztikus Turing-gép oldhatja meg . $(s (n))$ $s (n)$ $nem$ $(s (n))$ $s (n)$

A fent leírt számítási modellben, ha egy Turing-gép egy adott tér felhasználásával pozitív választ ad, akkor semmi sem eleve garantálja , hogy ez a tér elegendő ahhoz, hogy negatív választ adjon egy problémára, amelynek nincs megoldása: nem elég a számításokat figyelembe venni amelyek kudarcot vallottak a gépben, mivel nagyon nagyok lehetnek, vagy akár nem is korlátozott cellákon végződhetnek, és akkor hogyan lehet kiválasztani a legjobbat?

Tétel

Általános formájában az Immerman-Szelepcsényi-tétel kimondja az egyenlőséget:

{\ text {NSPACE}} (s (n)) = {\ text {co-NSPACE}} (s)

bármely funkcióhoz . $s (n) \ geq \ log n$

A tétel különleges esetként pozitív bizonyítékot ad a lineárisan korlátozott automatákra vonatkozó „második problémára” , és ezáltal azt bizonyítja, hogy a kontextus szerinti nyelvek halmazát kiegészítés zárja le, amely kérdés több mint három évtizede nyitva maradt.

Egy megfelelő nyilatkozat az NL és a co-NL komplexitási osztályokra vonatkozik . Valójában az NL az NSPACE rövidítése , azaz NL = NSPACE és hasonlóképpen co-NL = co-NSPACE . A nyilatkozat szerint: $(\ log (n))$ $(\ log (n))$ $(\ log (n))$

{\ text {NL}} = {\ text {co-NL}}

Látszólag alacsonyabb, mivel ez az első eset a sajátos eset , de az ebben az elméletben gyakran használt argumentum, amelyet kitöltési argumentumnak (in) hívnak (angolul argumentum kitöltés ), bizonyíthatja az ekvivalenciát. $s (n) = \ log n$

Tüntetések

A tétel igazolása elemi, de finom. Az eredmény önmagában alapvető és meglehetősen egyedülálló a komplexitáselméletben. Hasonló eredmény nem ismert az idő bonyolultsága tekintetében, és általában azt feltételezik, hogy az NP és a co-NP komplexitási osztályok eltérőek.

Megjelenése óta a tétel és annak bizonyítása a bonyolultságelmélet alapjainak részét képezi, ezért mesteri szinten tanítják őket, és oktatókönyvekben tartalmazzák. Különösen megemlíthetjük Papadimitriou, Arora és Barak könyveit.

Logaritmikus hierarchia

Ugyanebben a cikkben Immerman következményként bemutatja az NL osztály és a logaritmikus hierarchia közötti egyenlőséget , vagyis azokat a nyelveket, amelyeket a Turing-gépek váltogatnak , logaritmikus időben közvetlen hozzáféréssel és korlátozott számváltásokkal. Ehhez használja az NL osztály és az elsőrendű logika közötti egyenlőséget a tranzitív lezárással FO (Transitive closure) (en) , az egyenlőséget, amelyet a leíró bonyolultsággal hoz létre .

Megjegyzések

(in) árak Idézet Gödel 1995 ACM .
(en) Christos Papadimitriou , számítási komplexitás , Addison-Wesley ,1993( ISBN 978-0-201-53082-7 ).
(in) Sanjeev Arora és Boaz Barak , számítási komplexitás: A Modern Approach , Cambridge University Press ,2009( ISBN 0-521-42426-7 ).

(fr) Ez a cikk részben vagy egészben az „ Immerman - Szelepcsényi-tétel ” című angol Wikipedia cikkből származik ( lásd a szerzők felsorolását ) .

Függelékek

Kapcsolódó cikkek

Savitch tétele . Ez a tétel kapcsolatot hoz létre a térben a nem-determinisztikus bonyolultság osztályai és a determinisztikus megfelelőik között.

Külső hivatkozás

Lance Fortnow, A komplexitás alapjai, 19. lecke: Az Immerman - Szelepcsenyi-tétel . Újabb bizonyíték, az interneten.

Bibliográfia

Eredeti cikkek

N. Immerman, A nemdeterminisztikus tér kiegészítéssel zárva van , SIAM Journal on Computing, 17, 1988, pp. 935–938 .
Szelepcsényi Róbert, „A kényszerszámlálás módszere a nemdeterminisztikus automaták számára”. Acta Informatica vol. 26, n o 3, 1988, p. 279-284 . Előkiadvány, amelynek címe: „A nemdeterminisztikus automaták kényszerítésének módszere”, az EATCS Bulletin , vol. 33., 1987, p. 96–100 .

Kézikönyvek

(en) Christos H. Papadimitriou , Computational Complexity , Reading (Mass), Addison-Wesley , 1993 (újranyomás 1995-ös javításokkal), 523 p. ( ISBN 978-0-201-53082-7 és 0-201-53082-1 ) , p. 151-153.
en) Sanjeev Arora és Boaz Barak , Számítási bonyolultság: modern megközelítés , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , fej . 4 ("Űrösszetétel") pp. 91-92 .