Immerman – Szelepcsényiho věta - Immerman–Szelepcsényi theorem

v teorie výpočetní složitosti, Immerman – Szelepcsényiho věta tvrdí, že nedeterministický prostor třídy složitosti jsou uzavřeny doplňováním. Nezávisle to prokázal Neil Immerman a Róbert Szelepcsényi v roce 1987, pro který sdíleli rok 1995 Gödelova cena. Věta ve své obecné formě říká, že NSPACE (s(n)) = co-NSPACE (s(n)) pro jakoukoli funkci s(n) ≥ logn. Výsledek je ekvivalentně uveden jako NL = co-NL; i když se jedná o zvláštní případ, kdy s(n) = log n, implikuje obecnou větu standardem argument výplně.[1] Výsledek vyřešil druhý problém LBA.

Jinými slovy, pokud nedeterministický stroj dokáže vyřešit problém, může jiný stroj se stejnými mezemi zdrojů vyřešit doplněk problém (s Ano a Ne odpovědi obrácené) ve stejném asymptotickém množství prostoru. Žádný podobný výsledek není znám pro třídy časové složitosti a skutečně se o tom předpokládá NP se nerovná co-NP.

Princip používaný k prokázání věty se stal známým jako indukční počítání. Používá se také k prokázání dalších vět o výpočetní složitosti, včetně uzavření LOGCFL v rámci doplňování a existence bezchybných randomizovaných algoritmů logspace pro USTCON.[2]

Důkazní skica

Věta může být prokázána tím, že ukazuje, jak přeložit jakýkoli nedeterministický Turingův stroj M do jiného nedeterministického Turingova stroje, který řeší doplňkové rozhodovací problém pod Ó stejných prostorových omezení plus konstantní počet ukazatelů a čítačů, který potřebuje pouze a logaritmický množství prostoru.

Cílem je simulovat všechny konfigurace M, a zkontrolovat, zda nějaká konfigurace přijímá. To lze provést v NSPACE stejné velikosti, ale ke sledování konfigurací potřebuje také konstantní počet ukazatelů a čítačů. Pokud žádná konfigurace nepřijímá, simulující Turingův stroj přijímá vstup; přijímá tedy tehdy a jen tehdy, když M nemá žádnou cestu přijímání. Tato myšlenka je rozpracována v následujícím textu pro logaritmický NSPACE (NL ); zobecnění na větší NSPACE je jednoduché, ale může být také prokázáno polstrování.

Státy M (popsáno polohou jeho hlavy na vstupní pásce a konfigurací pracovní paměti log-space) lze považovat za vrcholy řízený graf a přechody z M lze v tomto grafu považovat za hrany. M přijímá vstupní řetězec, kdykoli v tomto grafu existuje cesta z vrcholu s který představuje počáteční stav zvláštního vrcholu t který představuje jakýkoli přijímající stát. Tímto způsobem existence existujícího nedeterministického výpočtu pro M lze považovat za verzi Svatý-konektivita problém, pro implicitní grafy spíše než grafy uvedené explicitně jako explicitně znázorněný vstupní graf. V tomto grafickém zobrazení je cílem důkazu najít nedeterministický algoritmus logického prostoru, který přijímá pouze tehdy, když ne existuje cesta z s na t ve stejném implicitním grafu.

Algoritmus, který řeší tento problém nedosažitelnosti, může být založen na principu počítání pro každé číslo i od 1 do n (pořadí implicitního grafu), číslo r vrcholů dosažitelných z s maximálně délkovými cestami i. Pokud je v kterékoli fázi algoritmu správná hodnota r je známý pro určitou hodnotu i, pak je možné otestovat, zda daný vrchol proti je dosažitelný z s maximálně délkovými cestami i + 1pomocí následujícího podprogramu:

  1. Li proti = s, návrat true
  2. Inicializovat počítadlo C na 0
  3. Pro každý vrchol u v implicitním grafu opakujte následující kroky:
    • Nedeterministicky hledat cestu délky nanejvýš i z s na u
    • Pokud cesta k u je nalezen, přírůstek C a otestujte, zda existuje hrana z u na proti
  4. Li C ≠ r, zastavit algoritmus a odmítnout vstup. V opačném případě vraťte true, pokud je hrana z u na proti bylo nalezeno a jinak falešné.

Při použití v rámci většího nedeterministického algoritmu mohou být jedinými akceptujícími výpočty algoritmu ty, ve kterých podprogram najde cesty ke všem dosažitelným vrcholům a vypočítá správnou odpověď, takže tento podprogram lze použít, jako by byl deterministický. S ním v ruce algoritmus pro testování nedosažitelnosti t z s lze vyjádřit následujícími kroky:

  1. Inicializovat i na 0 a r až 1
  2. Opakujte následující kroky n − 2 časy:
    • // r= # vrcholy dosažitelné uvnitř i kroky
    • Inicializovat počítadlo d na 0
    • Pro každý vrchol proti vyzkoušejte, zda proti je dosažitelný z s v rámci i + 1 kroky, a pokud ano, přírůstek d
    • Přírůstek i a nastavit r na d
  3. Vyzkoušejte, zda t je dosažitelný z s v rámci i + 1 kroky a odmítněte vstup, pokud je.
  4. Jinak, pokud i + 1 rovná se n, přijměte zadání.

Algoritmus potřebuje pouze udržovat reprezentace konstantního počtu čítačů a vrcholů v paměti, takže používá logaritmický prostor. Aplikováním tohoto algoritmu na implicitní graf vytvořený z daného nedeterministického stroje M, získá nedeterministický stroj pro doplňkový jazyk k jazyku, který přijímá M.

Hierarchie logického prostoru

Jako důsledek ve stejném článku to Immerman dokázal pomocí popisná složitost rovnost mezi NL a FO (přechodné uzavření), logaritmická hierarchie, tj. jazyky, o nichž rozhoduje střídavý Turingův stroj v logaritmickém prostoru s omezeným počtem střídání je stejná třída jako NL.

Viz také

  • Savitchova věta spojuje nedeterministické vesmírné třídy s jejich deterministickými protějšky

Poznámky

  1. ^ Standardní reference pro výplň ve složitosti prostoru (která předchází této větě) je Savitch, Walter J. (1970), „Vztahy mezi nedeterministickými a deterministickými složitostmi pásky“, Journal of Computer and System Sciences, 4: 177–192, doi:10.1016 / s0022-0000 (70) 80006-x, hdl:10338.dmlcz / 120475, PAN  0266702. Pro silnější argument výplně, který platí i pro třídy složitosti sublogaritmického prostoru, viz Szepietowski, Andrzej (1994), Turingovy stroje se sublogaritmickým prostorem, Přednášky v informatice, 843, Springer-Verlag, Berlín, doi:10.1007/3-540-58355-6, ISBN  3-540-58355-6, PAN  1314820.
  2. ^ Borodin, Allane; Cook, Stephen A.; Dymond, Patrick W .; Ruzzo, Walter L .; Tompa, Martin (1989), „Dvě aplikace indukčního počítání pro problémy s komplementací“, SIAM Journal on Computing, 18 (3): 559–578, CiteSeerX  10.1.1.394.1662, doi:10.1137/0218038.

Reference

externí odkazy