Popisná teorie složitosti

Popisná složitost je obor teorie výpočetní složitosti a teorie konečných modelů, který charakterizuje třídy složitosti podle typu logiky potřebné k vyjádření jazyků v nich. Například PH, spojení všech tříd složitosti v hierarchii polynomů, je právě třídou jazyků vyjádřitelnou výroky logiky druhého řádu. Toto spojení mezi složitostí a logikou konečných struktur umožňuje snadno přenášet výsledky z jedné oblasti do druhé, což usnadňuje nové důkazní metody a poskytuje dodatečný důkaz, že hlavní třídy složitosti jsou jaksi „přirozené“ a nejsou svázány s konkrétními abstraktními stroji používanými k jejich definování.

Prvním hlavním výsledkem popisné složitosti byla Faginova věta, kterou v roce 1974 ukázal Ronald Fagin. Ta stanovila, že NP je přesně množina jazyků vyjádřitelná větami existenciální logiky druhého řádu; to znamená logiky druhého řádu, která vylučuje univerzální kvantifikaci nad vztahy, funkcemi a podskupinami. Mnoho dalších tříd bylo později charakterizováno tímto způsobem, většinu z nich Neil Immerman:

Přesnější definice těchto tříd lze nalézt v článcích SO a FO.

Doporučujeme:  Kurt Gödel