Rekurze a strukturální složitost

Toto je jednoduchý prehľad s odkazom, kde hľadať ďalej.

Otázky sú:

• Aritmetická hierarchie tříd množin, třídy nekonečných větví rekurzivních stromů.

Pozri Prednášky z vyčísliteľnosti II. Pre hierarchiu TIN065_Prednáška_06#Aritmetická hierarchia a pre vetvy TIN065_Prednáška_09.

• Věta o nízké bázi.

$ A $ je low ak $ A'\leq_T \emptyset' $. Veta hovorí, že každá $ \Pi^0_1 $ trieda obsahuje nejakú low množinu.

• Diagonálně nerekurzivní funkce, význam a aplikace.

Vezmime funkciu $ J(e) = \varphi_e(e) $ (e-tý program na e). Funkcia $ f $ je diagonálne nerekurzívna ak $ f(e) \neq J(e) $ pre každé e, kde je $ J(e) $ definované.

• Základy aritmetického forcingu, 1-generické množiny.

Niečo málo na TIN065 Prednáška 10.

• Minimální stupně.

Možno TIN065 Prednáška 08.

• Algoritmická náhodnost, 1-náhodné množiny.

TIN065 Prednáška 11, ale hlavne článok Calibrating randomness (v zdrojoch tej prednášky).

• Strukturální složitost, Shanonova věta, pravděpodobnostní a neuniformní třídy složitosti, polynomiální hierarchie a vztah k ostatním třídám.

Shannonova veta je o minimálnej veľkosti Booleovských obvodov (pozri [1], originálny zdroj je na [2], ale ten čítať nikto asi nechce. Pre jednoduchý dôkaz podobného tvrdenia pozri Arora+Barak: Computational Complexity-Modern Approach, časť 6.3).

Pravdepodobnostné triedy sú rôzne RP, ZPP, BPP a PP. Definície napr. cez nedeterministické turingove stroje: Majme nedeterministický (no, skôr pravdepodobnostný) stroj, ktorý je presný (každý výpočet nad slovom dlhým n trvá práve n) a v každom kroku sa delí na dve vetvy (to sa dá). Potom jazyk je v RP ak pre slovo z jazyka aspoň polovica vetví prijíma a pre slovo nie z jazyka všetky neprijímajú. Jazyk je z PP ak aspoň polovica vetví určí slovo správne. Jazyk je v BPP ak slovo správne určí "clear majority", teda aspoň dve tretiny vetví. Jazyk je v ZPP ak mu pridáme stavy neviem a pre každé slovo skončí buď v stave neviem alebo v správnom stave (nikdy neurobí chybu) a počet správnych je viac ako nesprávnych. BPP je pokiaľ viem v $ \Pi_2 \cap \Sigma_2 $, ale neviem, či je to dôležité, PP obsahuje tuším celú PH.

Neuniformné triedy sú "tie s lomítkom". P/poly a P/log. Základné vety: P/poly jazyky sú práve tie, čo majú polynomiálne obvody (funkcia z poly mi vyrobí obvod, prípadne z obvodu funkciu). Existuje jazyk, čo je v EXPSPACE ale nie v P/poly (divný dôkaz s diagonalizáciou?). P/poly = $ \cup \{P(S), S \mbox{je riedka}\} $ (Jedným smerom vyberiem takú funkciu (v poly), ktorá vracia "dosť veľký kus S", druhým smerom zvolím takú riedku množinu, pomocou ktorej môžem f nagenerovať - budem sa pýtať, či mám prefix f a predlžovať ho). Ak SAT je v P/log, tak P = NP (opačný smer platí triviálne tiež, týmto smerom si viem všetky log funkcie v P nagenerovať, keď treba).

• Úplné problémy, řídké množiny a množiny nad jednoprvkovou abecedou a separace tříd složitosti pomocí nich.

Snáď ku každej triede je úplný nejaký SAT. A k NP je jazyk <M, x, 1^t>, kde NTS M príjme x za max t krokov (a podobný je pre PSPACE, akurát v priestore t).

Riedke množiny majú "málo" (polynomiálne mnoho) slov dĺžky n pre každé n. Tally množiny sú nad jednoprvkovou abecedou a zrejme sú riedke. $ \mbox{tally}(A) = \{1^{1\alpha}, \alpha \in A\} $ (alebo si proste očíslujem všetky stringy nad danou abecedou a pre A dám do tally(A) len tak dlhé postupnosti jedničie, že string s týmto číslom bol v A). $ A \in \mbox{DEXT} \iff \mbox{tally}(A) \in \mbox{P} $. $ A \in \mbox{NEXT} \iff \mbox{tally}(A) \in \mbox{NP} $.

DEXT je rôzne od NEXT práve keď existuje tally množina v NP-P a to práve keď existuje riedka množina v NP-P.

• Relativizace.

Celá relativizácia je pokus vyriešíť P vs. NP posunutím inde. A nedarí sa, lebo existuje orákulum, kde P(A)=NP(A) (vezmi PSAPCE úplné A a tam sa P(A) = PSPACE(A) = PSPACE), iné, kde sa nerovnajú (nejaká diagonalizácia), zasa iné, kde sa P(A) nerovná NP(A), ale NP(A)=PSPACE(A) a aj iné vety podobné.

Ďalej sa pridá trieda PQUERY(A) (polynomiálne mnoho dotazov na A v polyn. priestore). P(A) je v PQUERY(A) a to je v PSPACE(A). Snažíme sa oddeliť P a PSPACE. PQUERY(A) = P(QBF + A) pre všetky A (jeden smer - QBF riešim v priestore, ktorý mám, druhý smer pomocou QBF skáčem od dotazu k dotazu). P=PSPACE práve keď pre každé orákulum P(A) je rovné PQUERY(A) (jedným smerom prázdne orákulum, druhým predchádzajúcu vetu a QBF si spočítam v P ak sa PSPACE a P majú rovnať). Existuje orákulum A, že PQUERY(A) je rôzne od PSPACE(A).

Ešte máme NQUERY a takmer totožné tvrdenia. A ešte máme nejakú inú obmedzenosť pre orákula a NP.

• Biimunost a silná biimunost.

Pre triedu C je množina A imúnna ak žiadna jej nekonečná podmnožina nie je v C. Biimúnna je ak to platí aj pre doplnok A.

• Low and high hierarchie.

Low sú tie jazyky, ktoré keď strčíme stroju z polynomiálnej hierarchie ako orákulum, tak nám nepomôžu. High sú také, ktoré nám pomôžu preliezť na vyšší stupeň. Pozri wen:Low and high hierarchies a prvý odkazovaný článok. Vety: Ak Polynom. hierarchia kolabuje, tak všetky low aj high sú rovné NP, ak nekolabuje, tak prienik high a low je prázdny.

Ku témam z rekurzie je vhodná literatúra Nies: Computability and randomness, Piergiorgio Odifreddi. Forcing and Reducibilities (časť I by mohla stačiť) a Rod Downey, Denis R. Hirschfeldt, André Nies and Sebastiaan A. Terwijn: Calibratting Randomness (to je vlastne prednáška z rekurzie 2).

K témam zo zložitosti je najlepšie Structural complexity, pretože vlastne všetky prednášky zo zložitosti sú podľa toho (možno aj druhého dielu). Nejaká je aj v knižnici (aj na Karlíne).

K témam relativizace, biimunnost a low a high hierarchie je vhodna Structural Complexity II, dostupná nie len v knižnici (jeden kus), ale už aj v Studnici.