Beschrijvende Complexiteit

Beschrijvende complexiteit is een tak van complexiteitstheorie en modeltheorie, namelijk complexiteitsklassen gekenmerkt door het soort logica welke problemen kunnen worden beschreven.

Een van de voordelen van deze theorie is complexiteitsklassen definiëren zonder Turingmachines, dat een nieuwe kijk op bekende voorwerpen geeft. Bijvoorbeeld, de klasse NP is de verzameling van problemen die kunnen worden uitgedrukt met behulp van ESO vormen, een fragment van de tweede orde logica.

Definities

Bedenk dat een beslissing probleem kan worden beschreven door de taal van de lichamen worden geaccepteerd.

Informeel, een probleem is tot expressie in zekere zin, als er een formule van deze logica dat wordt voldaan door een model als en slechts als het model behoort tot de verzameling van geaccepteerde autoriteiten.

Voorbeelden

Interesses

De theorie van beschrijvende complexiteit kan aantonen dat de complexiteit klassen gedefinieerd met Turing machines zijn natuurlijk, in de zin dat ze verschijnen, zelfs als u geen conventionele modelberekeningen te gebruiken. Bovendien is deze theorie verschaft een nieuwe kijk op enige resultaten en sommige complexiteitstheorie gissingen, bijvoorbeeld de stelling van Abiteboul Vianu en geeft aan dat de klassen P en PSPACE gelijk als de logische inflatiedruk fixatiepunt en punt Partial Fix gelijk.

Resultaten

Het eerste resultaat van het domein, en een van de belangrijkste is de Fagin stelling die de gelijkwaardigheid tussen de klasse NP en expressie problemen bij ESO, de logica van de existentiële tweede orde geeft.

Vele andere klassen zijn gekarakteriseerd op dezelfde wijze omvatten:

• AC⁰, dat is de eerste orde logica;
• NL, dat is de eerste orde logica met transitieve afsluiting;
• PH dat is de tweede orde logica.
• EXPTIME is de logische volgorde met twee plaatsbepalingspunt.