Faginsova věta - Fagins theorem - Wikipedia

Faginova věta je nejstarším výsledkem teorie popisné složitosti, pobočka teorie výpočetní složitosti který charakterizuje třídy složitosti z hlediska logických popisů jejich problémů, spíše než chováním algoritmů pro řešení těchto problémů. Věta uvádí, že množina všech vlastností vyjádřitelných v existenciálním logika druhého řádu je přesně třída složitosti NP.

Bylo prokázáno Ronald Fagin v roce 1973 ve své disertační práci a objevil se ve své práci z roku 1974. The arity požadovaná vzorcem druhého řádu byla vylepšena (v jednom směru) v Lynchova věta a několik výsledků z Grandjean poskytly přísnější hranice pro nedeterministické náhodný přístup stroje.

Důkaz

Kromě Faginova článku z roku 1974 poskytuje Immerman 1999 podrobný důkaz věty. Je jednoduché ukázat, že každý existenciální vzorec druhého řádu lze rozpoznat v NP tím, že nedeterministicky vyberete hodnotu všech existenciálně kvalifikovaných proměnných, takže hlavní částí důkazu je ukázat, že každý jazyk v NP lze popsat pomocí existenciální vzorec druhého řádu. K tomu lze použít existenční kvantifikátory druhého řádu k libovolnému výběru výpočetního tabla. Podrobněji pro každou časovou stopu po spuštění nedeterministický Turingův stroj, toto tablo kóduje stav Turingova stroje, jeho pozici v pásku, obsah každé páskové buňky a kterou nedeterministickou volbu stroj v tomto kroku provede. Omezení této kódované informace tak, aby popisovalo platnou stopu provedení, ve které obsah pásky a stav a pozice Turingova stroje v každém časovém kroku vyplývají z předchozího časového postupu, lze poté vzorec prvního řádu.

Klíčovým lemmatem použitým v důkazu je, že je možné kódovat lineární pořadí délek nk (například lineární pořadí časových kroků a obsah pásky v libovolném časovém kroku) jako 2k-ary vztah R ve vesmíru A velikostin. Jedním ze způsobů, jak toho dosáhnout, je zvolit lineární uspořádání L z A a poté definovat R být lexikografické objednávání z k-tuples from A s ohledem naL.

Viz také

Reference

  • Immerman, Neil (1999). Popisná složitost. New York: Springer-Verlag. str. 113–119. ISBN  0-387-98600-6.

Další čtení