Popisná složitost
V teoretické informatice je popisná složitost odvětví teorie složitosti a teorie modelů , které charakterizuje třídy složitosti z hlediska logiky pro popis problémů.
Popisná složitost poskytuje nový úhel pohledu, protože definujeme třídy složitosti, aniž bychom se odvolávali na pojem strojů, jako jsou Turingovy stroje . Například třída NP odpovídá množině problémů vyjádřitelných v existenciální logice druhého řádu : je to Faginova věta .
Zásada
Příklad: vybarvení grafu
Vysvětlíme princip popisné složitosti s problémem 3-vybarvení grafu . Jde o rozhodovací problém, který spočívá v tom, že v grafu zjistíme, zda lze jeho vrcholy obarvit třemi barvami tak, aby dva sousední vrcholy neměly stejnou barvu. Na obrázku vpravo je uveden příklad tříbarevného grafu.
- Problém se 3 barvením je ve třídě NP . Vzhledem k vybarvení je skutečně snadné zkontrolovat (tj. V polynomiálním čase ve velikosti grafu), že dva sousední vrcholy nemají stejnou barvu.
- Na druhé straně je problém 3-vybarvení popsán vzorcem logiky dalšího existenčního druhého řádu . Tento vzorec zní „existuje jedna sada vrcholů C 1 , další sada vrcholů C 2 , další sada vrcholů C 3 (1, 2, 3 jsou tři možné barvy), například:
∃VS1,∃VS2,∃VS3,(∀s,⋁i=13VSi(s))∧(∀s⋀i,j=1i≠j3(¬VSi(s)∨¬VSj(s)))∧(∀t,R(s,t)→⋀i=13(¬VSi(s)∨¬VSi(t))){\ displaystyle \ existuje C_ {1}, \ existuje C_ {2}, \ existuje C_ {3}, \ left (\ forall s, \ bigvee _ {i = 1} ^ {3} C_ {i} (s) \ right) \ land \ left (\ forall s \ bigwedge _ {i, j = 1i \ neq j} ^ {3} (\ lnot C_ {i} (s) \ lor \ lnot C_ {j} (s)) \ right) \ land \ left (\ forall t, R (s, t) \ rightarrow \ bigwedge _ {i = 1} ^ {3} (\ lnot C_ {i} (s) \ lor \ lnot C_ {i} (t)) \ vpravo)}
- libovolný vrchol je barevný (libovolný vrchol je v jedné z podmnožin C i ),
- libovolný vrchol má nanejvýš jednu barvu (jakýkoli vrchol je nanejvýš v jedné z podmnožin C i ),
- dva sousední vrcholy mají různé barvy.
Rozhodovací problém jako dotaz
V popisné složitosti je tedy rozhodovací problém popsán logickým vzorcem, který odpovídá provedení dotazu (například dotaz „je graf 3 barevný?“). Příkladem rozhodovacího problému je model (například graf problému se 3 barvami je považován za model), na kterém lze vyhodnotit logické vzorce. Pozitivní případy rozhodovacího problému (tj. V příkladu 3barevných grafů) jsou přesně modely, ve kterých je vzorec pravdivý.
Další příklad
Zvažte rozhodovací problém A, který spočívá v určení, zda je graf G takový, že jakýkoli vrchol G připouští hranu dopadu. Graf G je považován za model, kde prvky domény jsou vrcholy grafu a vztah grafu je predikát . Rozhodovací problém A lze vyjádřit logikou prvního řádu, protože kladné instance jsou popsány vzorcem (jakýkoli vrchol s připouští nástupce t).
R{\ displaystyle R}∀s,∃t,sRt{\ displaystyle \ forall s, \ existuje t, sRt}
Faginova věta
Prvním výsledkem domény a jedním z nejdůležitějších je Faginova věta, která dává ekvivalenci mezi:
- třída NP , podle definice, třída rozhodovacích problémů, pro které lze snadno vyhledat řešení;
- a třída problémů vyjádřitelná v existenciální logice druhého řádu , tj. logika druhého řádu, kde jeden zakazuje univerzální kvantování predikátů a funkcí.
Korespondence mezi třídami a logikou
Mnoho dalších tříd bylo také charakterizováno stejným způsobem a jsou shrnuty v následující tabulce, většinou Neil Immerman .
Třídy složitosti
|
Odpovídající logika
|
---|
AC⁰
|
logika prvního řádu
|
NL
|
logika prvního řádu s přechodným uzávěrem
|
P
|
logika prvního řádu s nejmenším pevným bodem
|
NP
|
existenční logika druhého řádu
|
co-NP
|
univerzální logika druhého řádu
|
PH
|
logika druhého řádu
|
PSPACE
|
logika druhého řádu s přechodným uzavřením
|
EXPTIME
|
logika druhého řádu s nejmenším pevným bodem
|
ZÁKLADNÍ
|
logika vyššího řádu
|
RE
|
existenční logika prvního řádu na celá čísla
|
jádro
|
univerzální logika prvního řádu nad celými čísly
|
Příklad pro NL
Zájmy
Neil Immerman ospravedlňuje teorii popisné složitosti, protože ukazuje, že třídy složitosti definované pomocí Turingových strojů jsou přirozené : jsou definovatelné, i když nepoužíváme klasické výpočetní modely. Tato teorie navíc poskytuje nový pohled na určité výsledky a určité domněnky teorie složitosti, například věta Abiteboula a Vianu (en) naznačuje, že třídy P a PSPACE jsou stejné, pokud logický inflační pevný bod (IFP) a částečný Fixní bod (PFP) jsou stejné.
Externí odkaz
Stránka Neila Immermana o popisné složitosti s diagramem .
Varianty
Třída PTIME protínající invariantní problémy bisimulací odpovídá logice vícerozměrného mu-kalkulu .
Bibliografie
Články
- (en) Ronald Fagin , „ Zobecněná spektra prvního řádu a rozpoznatelné v polynomiálním čase “ , Proc. SIAM-AMS Sympos. Appl. Matematika. , Amer. Matematika. Soc., Sv. VII "Složitost výpočtu" ,1974, str. 43-73 ( Math Reviews 0371622 , číst online , přístup k 7. listopadu 2019 )
- (en) Neil Immerman , „ Jazyky, které zachycují třídy složitosti “ , STOC '83 Sborník z patnáctého ročníku ACM symposia o teorii práce s počítačem ,1983, str. 347-354 ( ISBN 0-89791-099-0 , DOI 10.1145 / 800061.808765 , číst online )
- (en) Serge Abiteboul et Victor Vianu , „ Generic Computation and its Complexity “ , STOC '91 Sborník z dvacátého třetího ročníku ACM symposia o teorii práce s počítačem ,1991, str. 209-219 ( ISBN 0-89791-397-3 , DOI 10.1145 / 103418.103444 )
Funguje
- (en) Neil Immerman , Descriptive Complexity , New York, Springer-Verlag,1999( ISBN 0-387-98600-6 , online prezentace )
- (en) Martin Grohe , Descriptive Complexity, Canonization, and Definable Graph Structure Theory , Cambridge University Press,2017, 554 s. ( ISBN 978-1-139-02886-8 , číst online ) , kap. I.3 („Popisná složitost“) , s. 40-93
Poznámky a odkazy
-
( Fagin 1974 ).
-
Zdroje důležitosti: Nyní jsme připraveni uvést Faginovu větu a Immerman-Vardiho větu, pravděpodobně dva nejzákladnější výsledky v teorii popisné složitosti. v ( Grohe 2017 )
-
Viz úvod ( Immerman 1983 ).
-
( Abiteboul a Vianu 1991 ).
-
Martin Otto , „ Bisimulation-invariant PTIME and higher-dimensional μ-calculus “, Theoretical Computer Science , sv. 224, n o 1,6. srpna 1999, str. 237–265 ( ISSN 0304-3975 , DOI 10.1016 / S0304-3975 (98) 00314-4 , číst online , přistupováno 22. listopadu 2019 )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">