Fagin tétele
Fagin tétele az algoritmusok bonyolultságának elméletének eredménye , amely bemutatja az NP osztály és az egzisztenciális másodrendű logikában kifejezhető problémakör egyenlőségét , vagyis a halmazokon az egzisztenciális kvantifikációk gazdagított első rendű logikáját. Ez a leíró bonyolultság alapító eredménye .
Ez az eredmény figyelemre méltó, mivel az NP osztályt jellemzi anélkül, hogy olyan számítási modell fogalmához kellene fordulnia, mint a Turing-gép .
Ennek az eredménynek a bizonyítékát 1973- ban Ronald Fagin bizonyította doktori disszertációjában. Azóta átdolgozták és továbbfejlesztették, különös tekintettel Lynch tételének és Grandjean eredményeinek.
Ennek a tételnek a bizonyítéka található Neil Immerman leíró összetettségű könyvében .
Példák
A háromszínű probléma NP-ben van, és a {G | írja le létezik a G csúcsainak háromszínű színe, az ilyen két szomszédos csúcs nem azonos színű}. Fagin tétele szerint az egzisztenciális másodrendű logika képlete írja le. Tény, hogy írják le a következő képlet: .
∃VS1,∃VS2,∃VS3,(∀s,⋁én=13VSén(s))∧(∀s⋀én,j=1én≠j3(¬VSén(s)∨¬VSj(s)))∧(∀t,R(s,t)→⋀én=13(¬VSén(s)∨¬VSén(t))){\ displaystyle \ létezik C_ {1}, \ létezik C_ {2}, \ létezik C_ {3}, \ bal (\ összes s, \ bigvee _ {i = 1} ^ {3} C_ {i} (s) \ jobb) \ land \ left (\ for s s bigwedge _ {i, j = 1i \ neq j} ^ {3} (\ lnot C_ {i} (s) \ lor \ lnot C_ {j} (s)) \ jobb) \ land \ left (\ összes t, R (s, t) \ rightarrow \ bigwedge _ {i = 1} ^ {3} (\ lnot C_ {i} (s) \ lor \ lnot C_ {i} (t)) \ jobbra}}
Például a szemközti gráf ennek a képletnek a modellje, mert három színnel színezhető.
Demonstráció
Bibliográfia
- (en) Ronald Fagin , „ Generalized First-Order Spectra and Polynomial-Time Recognizable Sets ” , SIAM-AMS Proceedings , vol. 7 "A számítás bonyolultsága" ,1974, P. 27-41 ( olvasható online , elérhető 1 -jén július 2010 )
- en) Neil Immerman , Leíró összetettség , New York, Springer-Verlag ,1999, 268 p. ( ISBN 0-387-98600-6 , online olvasás ) , p. 113-119
Referencia
(fr) Ez a cikk részben vagy egészben az
angol Wikipedia
" Fagin-tétel " című cikkéből származik
( lásd a szerzők felsorolását ) .
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">