TIN065 Prednáška 07

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

Máme tu siedmu prednášku, čo znamená, že by sme mali byť už za polovicou.

Na minulej prednáške sme sa začali zaoberať aritmetickou hierarchiou. Tak trochu s nadhľadom sme vynechávali premenné. Tiež sme si povedali, že hierarchie nie sú až tak zriedkavá vec. Jednu nájdeme v zložitosti - tam máme kvantifikátory obmedzené polynómom (asi ako "niečo existuje a je to nájditeľné v polynomiálnom čase"). Tiež je istá paralela medzi kvantifikátormi a operáciami zjednotenie a prienik (patrí do každej množiny, patrí do aspoň jednej množiny).

Pre pripomenutie: $ \Sigma $ sú tie, ktoré začínajú existenčným kvantifikátorom a $ \Pi $ sú tie, čo začínajú všeobecným. Triedy $ \Sigma_0 $ a $ \Pi_0 $ sú základné predikáty (bez kvantifikátorov, takže $ \Sigma_0=\Pi_0 $). V $ \Sigma_n $ a $ \Pi_n $ sú zasa tie predikáíty, ktoré sú vyjadriteľné ako predikáty s $ \Sigma_n $ alebo $ \Pi_n $ prefixom, čiže pred sebou majú n striedajúcich sa skupín kvantifikátorov. Dôležité je tiež, že prefix sa dá redukovať (v každej skupine ostane len jeden kvantifikátor) a obmedzené kvantifikátory nám nevadia (vieme sa ich zbaviť).

Aritmetický predikát je taký, ktorý má jeden z našich prefixov a zvyšok je záležitosťou predikátovej logiky (sú tam nejaké spojky a tak).

Presnejšie značenie je $ \Sigma_n^0 $, kde 0 znamená, že kvantifikujeme cez základné objekty (prirodzené čísla). 1 by znamenalo kvantifikovať cez funkcie, vyššie čísla cez niečo vyššie. To robiť nebudeme. V zložitosti sa dá stretnúť s označením $ \Sigma_n^p $, kde p znamená polynomiálnu hierarchiu. V značení je trochu neporiadok.

Celá hierarchia sa dá relativizovať a vzniknú nám $ \Sigma_n^{0,A} $ predikáty.

Príklad: Tot je $ \Pi_2 $. $ \mbox{Tot} = \{x:\forall y \exists s: \underbrace{\varphi_x(y)\downarrow \mbox{za } s\mbox{ krokov}}_\mbox{rekurzívna podmienka}\} $

Iný príklad: Rek: $ \mbox{Rek} = \{x:W_x \mbox{je rekurzívna}\} $. Každá $ W_x $ je rekurzívne spočetná (to vieme), len niektoré nie sú rekurzívne.$ x \in Rek \iff \overline{W_x} $ je rekurzívne spočetná (Postová veta) $ \iff \exists y (\overline{W_x} = W_y) $$ \iff \exists y (W_x \cup W_y = \mathbb{N} \And W_x \cap W_y = \emptyset) $$ \iff \exists y (\forall z (z \in W_x \cup W_y) \And \forall z (z \notin W_x \cap W_y)) $$ \iff \exists y (\forall z \exists s (z \in W_{x,s} \cup W_{y,s}) \And \forall z, s (z \notin W_{x,s} \cap W_{y,s})) $. V poslednom kroku už máme iba kvantifikátory na rekurzívnej podmienke (s je ako vždy počet krokov) a celé je to tvaru $ \exists (\forall \exists \And \forall) $, z čoho sa dá "šikovnými úpravami" nejak vyhrabať $ \exists \forall \exists (\mbox{rek. podm.}) $, takže to celé bude v $ \Sigma_3 $. Keby ostal čas a nezabudlo sa na to, na konci by sme si povedali prečo to lepšie nejde. Podobným spôsobom sa ukáže, že Fin je $ \Sigma_2 $.

Vetičky

  1. $ B\in \Sigma_n \iff \overline{B} \in \Pi_n $
  2. $ B\in \Sigma_n (\mbox{resp. } \Pi_n) \implies B \in \Sigma_m \cap \Pi_m $ pre $ m>n $
  3. $ A\leq_m B \And B\in \Sigma_n (\mbox {resp. } \Pi_n) \implies A\in \Sigma_n (\mbox {resp. } \Pi_n) $

Dôkaz:

  1. Triviálne z De Morganových pravidiel (teda, z toho, že $ \exists \neg \equiv \neg \forall $ a opačne).
  2. Druhé tvrdenie je len vyjadrením toho, že ak niečo ide jednoducho, ide to aj zložito. Ak potrebujem pridať kvantifikátor, tak si pridám fiktívnu premennú, ktorá nič nezmení a nepokazí. A kvantifikátor pridávam na koniec reťazca (akurát keď potrebujem zmeniť $ \Sigma $ na $ \Pi $ alebo späť, tak pridám jeden na začiatok) tak, by sa striedali.
  3. Mali sme vetu, ak $ A \leq_m B $ a B je rekurzívne spočetná, tak aj A je rekurzívne spočetná. Táto veta má rovnaký dôkaz. Ale predsa aspoň niečo: Nech $ B = \exists \forall \cdots Q(x, y_1, \ldots, y_n) $. Keďže sú m-prevoditeľné, tak existuje ORF f, že $ x \in A \iff f(x) \in B \iff \exists \forall \ldots Q(f(x), y_1, \ldots, y_n) $, kde to na konci je už vyjadrenie A v $ \Sigma_n $ (pre $ \Pi_n $ podobne).

Zaujíma nás, ako zapisovať množiny čo najjednoduchšie a ako táto hierarchia súvisí so skokom. A tiež nás zaujíma numerácia a indexácia.

Numerácia a indexácia

Vieme, že $ \Sigma_0=\Pi_0 $ nemajú univerzálny ORP. (sporom: Nech je $ R(e, x) $ e-ty ORP. Tak si vezmime $ \neg R(x, x) $, ktorý bude mať číslo $ e_0 $ a keď pustíme $ R(e_0, e_0) $, tak sa to bude rovnať svojej negácii).

Tiež vieme, že $ \Sigma_1 $ má univerzálny $ \Sigma_1 $ predikát. Ten pre jednu premennú má premenné dve a je tvaru $ \exists s T_1(e, x, s) $ a platí tam s-m-n veta.

Veta: Pre $ \forall n \geq 1 $ triedy $ \Sigma_n $ a $ \Pi_n $ majú univerzálny $ \Sigma_n $ a $ \Pi_n $ predikát. Dôsledkom je, že sa dá zaviesť pojem $ \Sigma_n $index, prípadne $ \Sigma_n $goedelového čísla. Univerzálny predikát nám poskytuje indexáciu a numeráciu a my vieme povedať, čo je to etý predikát.

Dokazuje sa to indukciou. Pre $ n=1 $ máme pre $ \Sigma_1 $ predikát $ \exists s T_1(e, x, s) $ a pre $ \Pi_1 $ $ \forall s \neg T_1(e, x, s) $. K $ \Pi_1 $: $ \Pi_1 $ je negáciou $ \Sigma_1 $, a z $ \neg \exists s T_1(e,x,s) $ vzniklo $ \forall s \neg T_1(e,x,s) $. Rovnako z univerzálneho predikátu k $ \Sigma_n $ vytvoríme univerzálny k $ \Pi_n $.

Nech n je nepárne. Náš $ \Sigma_n $ reťazec končí na $ \exists $ a vyzerá asi takto: $ \exists \forall \ldots \exists Q(x, y_1, \ldots, y_n) $. Odrežeme to pred posledným kvantifikátorom a dostaneme $ \exists y_n Q(x, y_1, \ldots, y_n) $, kde všetky premenné okrem $ y_n $ sú voľné. To je ekvivalentné s univerzálnym $ \Sigma_1 $ predikátom pre n premenných: $ \exists y_n T_n(e, x, y_1, \ldots, y_n) $ a k tomu prilepíme odtrhnuté kvantifikátory: $ \exists y_1 \forall y_2 \ldots \exists y_n T_n(e, x, y_1, \ldots, y_n) $, kde e je číslo predikátu a x je vstup.

Pre párne n je postup skoro rovnaký, len pri odtrhnutí $ \forall $ prejdem k negácii: z $ \forall Q() $ sa stane jednou negáciou $ \exists \neg Q() $, ktoré je ekvivalentné univerzálnemu $ \exists T_n() $ a z toho druhou negáciou späť na $ \forall \neg T_n() $. A k tomu pridám odrezané kvantifikátory.

Pre $ \Pi_n $ sa to dokazuje rovnako.

Pekným zistením je, že $ K\in \Sigma_1 - \Pi_1 $ (K je rekurzívne spočetná, ale jej doplnok už nie). Máme dokonca vetu:

Veta: $ \forall n \geq 1 : \Sigma_n - \Pi_n \neq \emptyset $.

Dôkaz: rovnaký ako pre n=1. Nech $ Univ^{(n)}(e, x) $ je univerzálny predikát pre $ \Sigma_n $. Vezmem $ P(x) = Univ^{(n)}(x,x) $. To, že je v $ \Sigma_n $ je vidieť a keby bol v $ \Pi_n $, tak jeho negácia by musela byť v $ \Sigma_n $. Tá má svoje číslo $ e_0 $ a je teda $ Univ^{(n)}(e_0, x) $. Teda $ \neg Univ^{(n)}(x, x) = Univ^{(n)}(e_0, x) $, čo pre $ x=e_0 $ dá spor. Takže $ P(x) $ je v $ \Sigma_n $ ale nie v $ \Pi_n $.

Fakt: $ \Sigma_1 \cap \Pi_1 = \Sigma_0 = \Pi_0 $ (to je Postova veta).

Uvidíme ale, že to neplatí pre vyššie $ \Sigma_n $. Už pre dvojku $ \Sigma_1\cup \Pi_1 $ je vlastnou podmnožinou $ \Sigma_2 \cap \Pi_2 $.

Veta o hierarchii:

  1. $ \forall n \geq 1: \emptyset^n $ je $ \Sigma_n $ úplná.
  2. A je rekurzívne spočetná v $ \emptyset^n \iff A \in \Sigma_{n+1} \forall n \geq 0 $
  3. $ A \leq_T \emptyset^n \iff A\in \Sigma_{n+1} \cap \Pi_{n+1} $

Túto vetu si dokážeme nabudúce.

Poznámky: $ \{A: A \leq_T \emptyset^{\prime}\} $ je viac ako $ \Sigma_1 \cup \Pi_1 $

$ \Sigma_1 $ sú rekurzívne spočetné množiny a $ \Pi_1 $ ich doplnky. Ale už netriviálna kombinácia množín z $ \Sigma_1 $ a $ \Pi_1 $ bude T-prevoditeľná na $ \emptyset^{\prime} $, ale nebude v $ \Sigma_1 \cup \Pi_1 $.

Príkladom je množina $ K\times \overline{K} $. Tá je T-prevoditeľná na $ \emptyset^{\prime} $. Ale zároveň $ K \leq_1 K\times \overline{K} $ (napr. funkciou $ x\to <x, z_0> $ a $ \overline{K} \leq_1 K\times \overline{K} $ napríklad funkciou $ x\to <z_0, x> $. A teda ak by $ K\times \overline{K} $ bolo v $ \Sigma_1 $, tak by tam musela byť aj $ \overline{K} $ a ak by $ K\times \overline{K} $ bolo v $ \Pi_1 $, tak by tam musela byť aj $ K $. A tie ako vieme tam nie sú.

A ešte definíciu pojmu, ktorý sme vo vete o hierarchii použili: A je $ \Sigma_n $ úplná ak je v $ \Sigma_n $ a hocijaká B zo $ \Sigma_n $ sa dá 1-previesť na A.

Poznámka: prečo v zložitosti nevieme tak pekne zistiť niektoré vzťahy (či niektoré triedy sú alebo nie sú zhodné)? Pretože si nemôžeme pomôcť univerzálnym polynómom. Taký proste nemáme.