SO (složitost) - SO (complexity)

Tento článek obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale jeho zdroje zůstávají nejasné, protože mu chybí vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Říjen 2020) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Logika druhého řádu je rozšířením první objednávka s druhá objednávka kvantifikátory, proto by si měl čtenář nejprve přečíst FO (složitost) abyste porozuměli tomuto článku. v popisná složitost vidíme, že jazyky rozpoznávané vzorci SO jsou přesně stejné jako jazyky, o kterých rozhoduje Turingovy stroje v polynomiální hierarchie. Rozšíření SO u některých operátorů nám také dávají stejnou expresivitu danou některými dobře známými třída složitosti,^[1] je to tedy způsob, jak dělat důkazy o složitosti některých problémů, aniž byste museli jít na algoritmické úroveň.

Definice a příklady

Definujeme proměnnou druhého řádu, proměnná SO má arity ${ displaystyle k}$ a představují jakýkoli výrok arity ${ displaystyle k}$, tj. podmnožina ${ displaystyle k}$- n-tice vesmíru. Obvykle jsou psány velkými písmeny. Logika druhého řádu je množina FO vzorce, kde přidáme kvantifikaci přes proměnné druhého řádu, proto použijeme termíny definované v FO článek, aniž byste je znovu definovali.

Vlastnictví

Normální forma

Každý vzorec je ekvivalentní vzorci v prenexové normální formě, kde nejprve napíšeme kvantifikaci na proměnnou druhého řádu a poté FO vzorec v prenexové normální formě.

Vztah ke třídám složitosti

SO se rovná Polynomiální hierarchie, přesněji máme tento vzorec v prenexové normální formě, kde se střídá existenciální a univerzální druhého řádu k časy jsou kúroveň polynomiální hierarchie.

To znamená, že SO pouze s existenční kvantifikací druhého řádu je rovno ${ displaystyle Sigma ^ {1}}$ který je NP a pouze s univerzální kvantifikací se rovná ${ displaystyle Pi ^ {1}}$ který je Co-NP.

Přidávání omezení

Hornovy vzorce jsou rovny P

SO (horn) je sada booleovských dotazů definovatelných pomocí vzorců SO v disjunktivní normální forma takové, že kvantifikátory prvního řádu jsou všechny univerzální a část vzorce bez kvantifikátoru je v Roh form, což znamená, že se jedná o velké AND OR, a v každém „OR“ jsou negovány všechny proměnné kromě jedné.

Tato třída se rovná P.

Tyto vzorce lze vytvořit v prenexové formě, kde druhý řád je existenční a první řád univerzální bez ztráty obecnosti.

Kromovy vzorce se rovnají NL

SO (Krom) je sada booleovských dotazů definovatelných pomocí vzorců druhého řádu v konjunktivní normální formě tak, že kvantifikátory prvního řádu jsou univerzální a část vzorce bez kvantifikátoru je v Krom form, což znamená, že vzorec prvního řádu je velký AND OR, a v každém „OR“ jsou maximálně dvě proměnné.

Tato třída se rovná NL.

Tyto vzorce lze vytvořit v prenexové formě, kde druhý řád je existenční a první řád univerzální bez ztráty obecnosti.

Tranzitivní uzavření je PSPACE

SO (TC) je tedy SO FO (TC) je FO. Operátor TC může nyní jako argument brát také proměnnou druhého řádu. SO (TC) se rovná PSPACE.

Nejméně pevným bodem je EXPTIME

SO (LFP) je tedy SO FO (LFP) je FO. Operátor LFP nyní může jako argument brát také proměnnou druhého řádu. SO (LFP) se rovná EXPTIME.

Iterující

TAK(t(n)) je SO co FO [t(n)] je FO. Ale nyní máme v bloku kvantifikátoru také kvantifikátor druhého řádu. Je známo že:

• ${ displaystyle { mathsf {SO}} [n ^ {O (1)}]}$ je rovný PSPACE je to také další způsob zápisu SO (TC).
• ${ displaystyle { mathsf {SO}} [2 ^ {n ^ {O (1)}}]}$ je rovný EXPTIME je to také další způsob zápisu SO (LFP)

Viz také

• První objednávka
• Vysoká objednávka

Reference

externí odkazy

• Složitost zoo o SO, podívejte se také na třídu pod ním.