PRŮBĚH PŘEDNÁŠKY VÝPOČTOVÁ SLOŽITOST (ZIMNÍ SEMESTR 2007/2008) ========================== 9.10.2007 ============================== Budeme se zabývat tím, jak velký prostor a čas je potřebný k řešení úloh na počítači. Algoritmicky neřešitelné úlohy: - L(G) = \Sigma^* - L(G_1) \cap L(G_2) \not= 0 - problém slov v obecné asociativní algebře - polynomiální rovnice více proměnných v přirozených číslech (důkaz neřešitelnosti pochází od Matijaseviče, 10. Hilb. problém) Příklady náročných úloh: - problém obchodního cestujícího (TSP) - konečné hry (šachy, go, hra na grafech) - problém splnitelnosti výrokových formulí (SAT) Algoritmus násobení n bitových čísel složitosti n^log_2 3. Existuje algoritmus složitosti O(n log n log log n). Připomenuto značení O(f), \Omega(f). ========================== 16.10.2007 ============================== Algoritmická neřešitelnost polynomiálních rovnic v celých číslech. Položena otázka úspornější parametrizace n přirozených čísel pomocí celých čísel než pomocí 4n parametrů. Důkaz vzájemné převoditelnosti následujících problémů (A) splnitelnost Booleovských formulí v KNF (B) řešitelnost soustav polynomiálních rovnic v tělese Z_2. (C) splnitelnost obecných Booleovských formulí v bázi všech binárních spojek Převod úlohy typu (A) na (B) pomocí přepisu klausule l_1, ..., l_k na polynom (1 - (1 - l_1)...(1 - l_k)). Převod úlohy typu (B) na (C) lze provést náhradou násobení za konjunkci a sčítání za nonekvivalenci. Převod úlohy typu (C) na (A) vyžaduje přidání nových proměnných, které popisují hodnoty všech podformulí. S pomocí těchto nových proměnných se vyhodnocení formule popíše pomocí lokálních podmínek svazujících každou podformuli s jejími bezprostředními podformulemi. Shrnuty pojmy - rozhodovací úloha - výpočet funkce - vyhledávací úloha Zaveden pojem optimalizační úloha. ========================== 23.10.2007 ============================== - Příklady optimalizačních úloh, rozhodovací varianta, výpočet optima, hledání optimálního řešení. - Zavedení TS s jednou a více páskami, kopírování s jednou a dvěma páskami. - Značení pro čas t(w), t(n) a prostor s(w), s(n) pro konkrétní TS. Výpočty s prostorovou složitostí menší než n. - RAM, jednotková a logaritmická (bitová) složitost. - RAM s násobením. Jednotková a bitová složitost n násobného umocnění na druhou. - RAM bez násobení a dělení. Složitost operace trunc(x/2). Poznámka: Navržený algoritmus pro trunc(x/2) s konstantním prostorem má jednotkovou složitost O(n^2), kde n je délka zápisu x. - Požadavek rozumného kódování. Musí být efektivní (nejvýše polynomiální) převod mezi kódem a původní strukturou v modelu, kdy můžeme přímo pracovat s libovolnými kombinatorickými strukturami. Není to exaktně definovaný pojem, protože není formálně zaveden potřebný výpočetní model. Zmínka o problému testování a^b \lt c^d pro n bitová čísla. Poznámka: V roce 1796 dokázal Gauss, že každé přirozené číslo je součtem tří trojúhelníkových čísel, což jsou čísla tvaru n(n+1)/2, tedy choose(n+1,2). ========================== 30.10.2007 ============================== Transformace rovnice n proměnných z N na 1. rovnici s 11 proměnnými ze Z pomocí zesílení Matijasevičovy věty 2. rovnici s 3n proměnnými ze Z pomocí Gaussova výsledku o součtu tří trojúhelníkových čísel. Hledání splňujícího ohodnocení výrokové formule pomocí testu splnitelnosti. Hledání Hamiltonovské kružnice pomocí testu přítomnosti takové kružnice. Úvaha o hledání důkazu matematické věty pomocí testu dokazatelnosti. Poznámka, že algoritmicky nerozhodnutelný problém musí obsahovat instance nezávislé na teorii množin. Konstrukce jazyka L_f pro danou funkci s polynomiálně omezenou délkou výstupu. Důkaz, že L_f je v P právě když f je vyčíslitelná v polynomiálním čase. Zavedení tříd DTIME(t) a DSPACE(s). Blumova věta o (exponenciálním) zrychlení. Důsledek: nelze definovat složitost úlohy, jen algoritmu. Složitost úlohy lze charakterizovat jen tím, zda L patří do DTIME(t) nebo DSPACE(s) pro konkrétní míry složitosti t,s. Množina takových t,s nemusí mít minimum. Zmínka o větě o dírách a o konstruovatelnosti. Zavedení Booleovských obvodů. Transformace polynomiálního výpočtu TS na polynomiálně velký obvod. Neuniformní modely. TS s pomocnou funkcí alpha. ========================== 6.11.2007 ============================== Algoritmy na RAM bez dělení a násobení pro výpočet trunc(x/2) s konstantní pamětí. Zavedení P/poly, LOGSPACE/poly. formule \subseteq LOGSPACE/poly (bez důkazu). obvody = P/poly (bez důkazu). Toto dává do souvislosti porovnání síly výrokových formulí a obvodů s porovnáním neuniformních variant tříd LOGSPACE a P, o kterých se předpokládá, že vnoření LOGSPACE do P je ostré. STCONN je v DSPACE(log^2 n). USTCONN je v DSPACE(log n) = LOGSPACE. Pravděpodobnostní TS. Polynomiální pravděpodobnostní TS lze simulovat ve třídě P/poly. Ekvivalence read-once rozhodovacích diagramů je rozhodnutelná pravděpodobnostním TS v poly čase. (Stroj může nezjistit neekvivalenci, ale nemůže udělat chybu, pokud jsou ekvivalentní.) Interaktivní pravděpodobnostní důkaz neizomorfnosti dvou grafů. ========================== 13.11.2007 ============================== LOGSPACE \subseteq P. Také LOGSPACE/poly \subseteq P/poly. Polynomiální formule pro maticovou funkci "v každém sloupci dvě jedničky po sobě". Logaritmický prostor na TS pro tuto úlohu. Programovací jazyk pro TS. Simulace k-páskoveho 1-páskovým TS. Náznak simulace k-páskového 2-páskovým TS. Uložení registrů RAM na pásce TS. ========================== 20.11.2007 ============================== Simulace RAM pomocí TS. Simulace RAM pomocí efektivně konstruovatelných obvodů. Ekvivalence P/poly a obecných obvodů. Zavedení p-převoditelnosti. SAT je p-převeditelný na problém klika v grafu. ========================== 27.11.2007 ============================== p-převoditelnost problému kliky na SAT. Splnitelnost Booleovských obvodů je NP-úplná úloha. Vyjádření lokálních podmínek pro splnění obvodů dává formuli v KNF, což dokazuje NP-úplnost SAT. p-převoditelnost SAT na 3-SAT. ========================== 4.12.2007 ============================== NP-úplnost problému přesného 3-pokrytí. Vzájemná p-převoditelnost problému batohu s přirozenými a s celými čísly. NP-úplnost problému batohu s přirozenými čísly převodem z 3-SAT. ========================== 11.12.2007 ============================== Problém batohu s celými čísly. Problém rozdělení v přirozených a celých číslech. Ekvivalence všech uvedených variant problému batohu. Problém batohu lze řešit v čase, který je polynomiální v hodnotách čísel n,b. Věta o úplnosti rezoluce (zatím bez důkazu). Důsledek: 2-SAT je v P. Nedokončené řešení 2-SAT pomocí grafu. Zavedení aproximačních algoritmů. Problém vrcholového pokrytí a jeho souvislost s problémem kliky (zatím bez důkazu). ========================== 18.12.2007 ============================== Vzájemná p-převeditelnost problému kliky a vrcholového pokrytí. Dokončení testu 2-SAT přes tranzitivní uzávěr implikací. Důkaz úplnosti rezoluční metody. Aproximační algoritmus pro vrcholové pokrytí s faktorem 2.