ELEMENTARY (složitost)
V teorii složitosti se ELEMENTARY složitost třída z elementárních rekurzivních funkcí je spojení tříd v exponenciální hierarchie .
ELEMENETNARY=EXPTJáME∪2EXPTJáME∪3EXPTJáME∪⋯=DTJáME(2ne)∪DTJáME(22ne)∪DTJáME(222ne)∪⋯{\ displaystyle {\ begin {aligned} \ mathrm {ELEMENTARY} & = \ mathrm {EXPTIME} \ cup \ mathrm {2EXPTIME} \ cup \ mathrm {3EXPTIME} \ cup \ cdots \\ & = \ mathrm {DTIME} (2 ^ {n}) \ cup \ mathrm {DTIME} (2 ^ {2 ^ {n}}) \ cup \ mathrm {DTIME} (2 ^ {2 ^ {2 ^ {n}}}) \ cup \ cdots \ konec {zarovnáno}}}Název zavedl László Kalmár v souvislosti s vypočítatelnými funkcemi a nerozhodnutelností, kde většina problémů není elementární. Rozhodovací problém se říká, že je neelementární, pokud není v ELEMENTARY.
Definice
Definice elementárních rekurzivních funkcí je stejná jako definice rekurzivních primitivních funkcí , kromě toho, že primitivní rekurzivní konstrukční schéma je nahrazeno součtem a omezeným součinem. Všechny funkce působí na přirozená čísla . Základní funkce jsou:
- Funkce null . Neustále nula :;F(X)=0{\ displaystyle f (x) = 0}
- Funkce nástupce : který je často označován S . Opakováním této funkce získáme sčítání;F(X)=X+1{\ displaystyle f (x) = x + 1}
- Tyto projekce : Tato funkce slouží k ignorovat argumenty. Například je projekce;F(na,b)=na{\ displaystyle f (a, b) = a}
- Odčítání : v případě , nebo 0, pokud . Tato funkce se používá k vytváření podmínek a k iteraci.F(X,y)=X-y{\ displaystyle f (x, y) = xy}y<X{\ displaystyle y <x}y⩾X{\ displaystyle y \ geqslant x}
Z těchto základních funkcí lze vytvořit další funkce.
- Kompozice elementárních funkcí. je základní, jestliže a všechny z nich jsou základní.F(X1,...,Xne)=h(G1(X1,...,Xne),...,Gm(X1,...,Xne)){\ displaystyle f (x_ {1}, \ ldots, x_ {n}) = h (g_ {1} (x_ {1}, \ ldots, x_ {n}), \ ldots, g_ {m} (x_ { 1}, \ ldots, x_ {n}))}h{\ displaystyle h}Gi{\ displaystyle g_ {i}}
-
Vázaný součet : je elementární, pokud je elementární.F(m,X1,...,Xne)=∑i=0mG(i,X1,...,Xne){\ displaystyle f (m, x_ {1}, \ ldots, x_ {n}) = \ součet \ limity _ {i = 0} ^ {m} g (i, x_ {1}, \ ldots, x_ {n })}G{\ displaystyle g}
-
Ohraničený produkt : je elementární, pokud je elementární.F(m,X1,...,Xne)=∏i=0mG(i,X1,...,Xne){\ displaystyle f (m, x_ {1}, \ ldots, x_ {n}) = \ prod \ limity _ {i = 0} ^ {m} g (i, x_ {1}, \ ldots, x_ {n })}G{\ displaystyle g}
Nižší základní rekurzivní funkce
Dolní základní rekurzivní funkce se řídí předchozí definicí, kromě toho, že vylučujeme ohraničený produkt. Funkce je tedy nižší základní, pokud se jedná o projekci, nástupce, nulovou funkci nebo složený nebo ohraničený součet jiné nižší základní funkce.
Zatímco elementární funkce mohou růst exponenciálně a obsahovat exponenciální hierarchii, nižší elementární funkce mají pouze polynomiální růsty.
Základní funkce ELEMENTARY
Třída elementárních funkcí shoduje s uzávěrem složením výstupků a jedné z následujících funkčních skupin: , , , který je v odčítání je definováno výše.
{ne+1,ne-.m,⌊ne/m⌋,nem}{\ displaystyle \ {n + 1, n \, {\ stackrel {.} {-}} \, m, \ lfloor n / m \ rfloor, n ^ {m} \}}{ne+m,ne-.m,⌊ne/m⌋,2ne}{\ displaystyle \ {n + m, n \, {\ stackrel {.} {-}} \, m, \ lfloor n / m \ rfloor, 2 ^ {n} \}}{ne+m,ne2,nemodm,2ne}{\ displaystyle \ {n + m, n ^ {2}, n \, {\ bmod {\,}} m, 2 ^ {n} \}}ne-.m=max{ne-m,0}{\ displaystyle n \, {\ stackrel {.} {-}} \, m = \ max \ {nm, 0 \}}NE{\ displaystyle \ mathbb {N}}
Příklady
Funkce , a jsou základní. První lze snadno zkonstruovat ohraničeným součtem, druhou ohraničeným součinem. Poslední vyžaduje trochu více práce a používá přirozené odčítání.
(X,y)↦Xy{\ displaystyle (x, y) \ mapsto xy}(X,y)↦Xy{\ displaystyle (x, y) \ mapsto x ^ {y}}X↦X!{\ displaystyle x \ mapsto x!}
Vztahy mezi třídami
Některé přirozené rekurzivní problémy jsou mimo ELEMENTARY a proto jsou ve NONELEMENTARY třídě. Zejména existují některé rekurzivní primitivní problémy, které nejsou v ELEMENTARY. Víme, že
MÉNĚ ELEMENTARY
EXPTIME ELEMENTARY
PR R⊊{\ displaystyle \ subsetneq} ⊊{\ displaystyle \ subsetneq}⊊{\ displaystyle \ subsetneq} ⊊{\ displaystyle \ subsetneq}
Zatímco ELEMENTARY obsahuje pouze ohraničené iterace umocňování (např. ), PR umožňuje obecnější hyperoperace (např. Tetrace ), které nejsou v ELEMENTARY
Ó(22ne){\ displaystyle O (2 ^ {2 ^ {n}})}
Vlastnosti
Pro jakoukoli funkci můžeme definovat její omezenou minimalizaci označenou jako funkci
F:NEk+1→NEr{\ displaystyle f: \ mathbb {N} ^ {k + 1} \ rightarrow \ mathbb {N} ^ {r}}MineB(F){\ displaystyle \ mathrm {MinB} (f)}
MineB(F):NEk+1→NE(ne,m)↦{min{i⩽ne∣F(i,m)=dr(0)}pokud existuje ine+1Pokud ne{\ displaystyle {\ begin {zarovnáno} \ mathrm {MinB} (f): \ mathbb {N} ^ {k + 1} & \ rightarrow \ mathbb {N} \\ (n, m) & \ mapsto {\ begin {cases} \ min \ {i \ leqslant n \ mid f (i, m) = d_ {r} (0) \} & {\ text {pokud existuje takový}} i \\ n + 1 & {\ text {jinak}} \ end {cases}} \ end {zarovnáno}}}
kde označuje -tuplet .
dr(X){\ displaystyle d_ {r} (x)}r{\ displaystyle r}(X,...,X){\ displaystyle (x, \ ldots, x)}
ELEMENTARY je stabilní omezenou minimalizací.
Demonstrace
Buď . Pózujeme ( což představuje přirozené odčítání)
F∈ELEMENETNARY(NEne×NE,NEm){\ displaystyle f \ v ELEMENTARY (\ mathbb {N} ^ {n} \ times \ mathbb {N}, \ mathbb {N} ^ {m})}-˙{\ displaystyle {\ dot {-}}}
h(u,y)=∑i=0y(1-˙F(u,i))){\ displaystyle h (u, y) = \ součet \ limity _ {i = 0} ^ {y} (1 {\ dot {-}} f (u, i)))}
kde a
a
u∈NEne{\ displaystyle u \ in \ mathbb {N} ^ {n}}y∈NE{\ displaystyle y \ in \ mathbb {N}}
G(u,X)=h(u,y)(1-˙(h(u,X)-˙X)){\ displaystyle g (u, x) = h (u, y) (1 {\ dot {-}} (h (u, x) {\ dot {-}} x))}
Pak máme nebo je jasně elementární, protože jsme získali produktem, rozdílem a ohraničeným součtem. Omezená minimalizace elementární funkce je tedy elementární.
MineB(y↦F(u,y))(X)=G(u,X){\ displaystyle \ mathrm {MinB} (y \ mapsto f (u, y)) (x) = g (u, x)}G{\ displaystyle g}
Buď , a . Definujeme rekurzí ohraničenou funkcí definovanou
F:NEk→NEr{\ displaystyle f: \ mathbb {N} ^ {k} \ rightarrow \ mathbb {N} ^ {r}}G:NEk+r+1→NEr{\ displaystyle g: \ mathbb {N} ^ {k + r + 1} \ rightarrow \ mathbb {N} ^ {r}}j:NEk+1→NEr{\ displaystyle j: \ mathbb {N} ^ {k + 1} \ rightarrow \ mathbb {N} ^ {r}}h=REvs.B(F,G,j){\ displaystyle h = \ mathrm {RecB} (f, g, j)}
h(0,m)=F(m)h(ne+1,m)=G(ne,h(ne,m)m){\ displaystyle {\ begin {zarovnáno} h (0, m) & = f (m) \\ h (n + 1, m) & = g (n, h (n, m) m) \ end {zarovnáno} }}
a kdo by to měl zkontrolovat
. se nepoužívá k sestavení funkce, ale slouží jako certifikát pro její růst.
h(ne,m)⩽j(ne,m){\ Displaystyle h (n, m) \ leqslant j (n, m)}j{\ displaystyle j}
ELEMENTARY je stabilní omezenou rekurzí.
Základní predikáty
Definice
O predikátu se říká, že je elementární, pokud je jeho indikátorová funkce elementární funkcí.
Vlastnosti
Pojďme být predikátem . Omezené kvantizace tohoto predikátu nazýváme predikátyP{\ displaystyle P}NEk+1{\ displaystyle \ mathbb {N} ^ {k + 1}}NEk{\ displaystyle \ mathbb {N} ^ {k}}
∀i⩽ne,P(i,m)∃i⩽ne:P(i,m){\ displaystyle {\ begin {zarovnáno} \ forall i \ leqslant n, & P (i, m) \\\ existuje i \ leqslant n: & P (i, m) \ end {zarovnáno}}}
pro všechny přirozené .
ne{\ displaystyle n}
Třída elementárních predikátů je stabilní omezenou kvantizací.
Elementární predikát třída je stabilní pro logické operace , a .
¬{\ displaystyle \ neg}∧{\ displaystyle \ klín}∨{\ displaystyle \ vee}
Popisná charakterizace
V popisné složitosti se ELEMENTARY rovná třídě HO . To znamená, že jakýkoli jazyk ELEMENTARY lze popsat jako vzorec HO, který platí pouze pro prvky HO. Přesněji řečeno , kde označuje řadu umocňování a je třídou vzorců, které začínají existenciálními kvantifikátory tého řádu, a tedy vzorcem ( i - 1) tého řádu.
NETJáME(22⋰ 2Ó(ne))=∃HÓi{\ displaystyle \ mathrm {NTIME} (2 ^ {2 ^ {{\ text {⋰}} ^ {2 ^ {O (n)}}}}) = \ existuje {} HO ^ {i}}⋰ {\ displaystyle {\ text {⋰}}}i{\ displaystyle i}∃HÓi{\ displaystyle \ existuje {} HO ^ {i}}i{\ displaystyle i}
externí odkazy
Reference
-
Mazzanti, S., „Prostý základ pro třídy primitivních rekurzivních funkcí“, Mathematical Logic Quarterly, 48 (2002) 93–104
-
Lauri Hella a José María Turull-Torres, Výpočetní dotazy s logikou vyššího řádu , sv. 355, Essex, Velká Británie, Elsevier Science Publishers Ltd.,2006, 197–214 s. ( ISSN 0304-3975 , DOI 10.1016 / j.tcs.2006.01.009 , číst online )
- Rose, HE, „Subrecursion: Functions and hierarchies“, Oxford University Press, New York, USA, 1984. ( ISBN 0-19-853189-3 )
Podívejte se také
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">