Popisná teorie složitosti - Descriptive complexity theory

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (prosinec 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Popisná složitost je pobočkou teorie výpočetní složitosti a ze dne teorie konečných modelů který charakterizuje třídy složitosti podle typu logika potřebné k vyjádření jazyků v nich. Například, PH, spojení všech tříd složitosti v polynomiální hierarchii, je přesně ta třída jazyků, která je vyjádřitelná příkazy logika druhého řádu. Toto spojení mezi složitostí a logikou konečných struktur umožňuje snadný přenos výsledků z jedné oblasti do druhé, což usnadňuje nové důkazní metody a poskytuje další důkaz, že hlavní třídy složitosti jsou jaksi „přirozené“ a nejsou vázány na konkrétní abstraktní stroje slouží k jejich definování.

Konkrétně každý logický systém produkuje sadu dotazy vyjádřitelný v něm. Dotazy - pokud jsou omezeny na konečné struktury - odpovídají výpočetní problémy tradiční teorie složitosti.

Prvním hlavním výsledkem popisné složitosti bylo Faginova věta, zobrazeno Ronald Fagin v roce 1974. To prokázalo NP je přesně sada jazyků vyjádřitelných existenčními větami logika druhého řádu; to je logika druhého řádu s vyloučením univerzální kvantifikace vztahů, funkcí a podmnožin. Mnoho dalších tříd bylo později charakterizováno takovým způsobem, většina z nich Neil Immerman:

• Logika prvního řádu definuje třídu FO, souhlasí s AC⁰, jazyky rozpoznané obvody polynomiální velikosti ohraničené hloubky, která se rovná jazykům rozpoznávaným a souběžný stroj s náhodným přístupem v konstantním čase.
• Logika prvního řádu s komutativem, přechodné uzavření operátor přidal výnosy SL, což se rovná L, problémy řešitelné v logaritmickém prostoru.
• Logika prvního řádu s a přechodné uzavření výnosy operátora NL, problémy řešitelné v nedeterministickém logaritmickém prostoru.
• V přítomnosti lineárního řádu, logika prvního řádu s a nejméně pevný bod operátor dává P, problémy řešitelné v deterministickém polynomiálním čase.
• Existenční výnosy logiky druhého řádu NP.
• Univerzální logika druhého řádu (s výjimkou existenční kvantifikace druhého řádu) poskytuje co-NP.
• Druhá objednávka logika odpovídá PH, jak je zmíněno výše.
• Logika druhého řádu s a přechodné uzavření (komutativní nebo ne) výnosy PSPACE, problémy řešitelné v polynomiálním prostoru.
• Logika druhého řádu s a nejméně pevný bod operátor dává EXPTIME, problémy řešitelné v exponenciálním čase.
• ${ displaystyle existuje { color {modrá} { mathsf {HO}}} ^ {i}}$, logika s existenčním kvantifikátorem objednávky i následuje vzorec pořadí ${ displaystyle i-1}$ je rovný ${ displaystyle { color {modrá} { mathsf {NTIME}}} ( exp _ {2} ^ {i-2} (n ^ {O (1)}))}$^[1]
• ${ displaystyle { mathsf {HO}} _ {j} ^ {i} = { color {modrá} { mathsf {NTIME}}} ( exp _ {2} ^ {i-2} (n ^ { O (1)})) ^ { Sigma _ {j} ^ { mathsf {P}}}}$
• HO je rovný ZÁKLADNÍ

Viz také

• SO (složitost)
• FO (složitost)
• Spektrum věty

Reference

• Ronald Fagin, Zobecněná spektra prvního řádu a sady rozpoznatelných v polynomiálním čase. Složitost výpočtu, vyd. R. Karp, SIAM-AMS Proceedings 7, s. 27–41. 1974.
• Fagin, Ronald (1993). „Teorie konečných modelů - osobní perspektiva“. Teoretická informatika. 116: 3–31. doi:10.1016 / 0304-3975 (93) 90218-i.
• Immerman, Neil (1983). "Jazyky, které zachycují třídy složitosti". Sborník z patnáctého výročního symposia ACM o teorii práce s počítači - STOC '83. str. 347–354. doi:10.1145/800061.808765. ISBN  0897910990.
• Immerman, Neil (1999). Popisná složitost. New York: Springer-Verlag. str. 113–119. ISBN  0-387-98600-6..

Další čtení

• Shawn Hedman, První kurz v logice: úvod do teorie modelů, teorie důkazů, vypočítatelnosti a složitostiOxford University Press, 2004, ISBN  0-19-852981-3, oddíl 10.3 je vhodným úvodem pro vysokoškoláky
• Grädel, Erich; Kolaitis, Phokion G .; Libkin, Leonid; Maarten, Marx; Spencer, Joel; Vardi, Moshe Y.; Venema, Yde; Weinstein, Scott (2007). Teorie konečných modelů a její aplikace. Texty v teoretické informatice. Řada EATCS. Berlín: Springer-Verlag. ISBN  978-3-540-00428-8. Zbl  1133.03001.

externí odkazy

• Stránka s popisnou složitostí Neila Immermana, včetně diagramu