TIN065 Prednáška 07

Prednášky z Vyčísliteľnosti II
Obsah
Prehľad Prvá prednáška Druhá prednáška Tretia prednáška Štvrtá prednáška Piata prednáška Šiesta prednáška Siedma prednáška Ôsma prednáška Deviata prednáška Desiata prednáška Jedenásta prednáška Dvanásta prednáška Zhrnutie na skúšku

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.