PRŮBĚH PŘEDNÁŠKY VÝPOČETNÍ SLOŽITOST (LETNÍ SEMESTR 2015/2016) =================================== 16.2.2016 =================================== Problém CSAT je NP-úplný. Důkazy p-převoditelností: CSAT na SAT, SAT na 3-SAT, 3-SAT na přesné 3-pokrytí. =================================== 17.2.2016 =================================== NP-úplnost problémů: batohu, půlení, Hamiltonovské kružnice, metrická varianta TSP. Zmínka o MAX-SAT. =================================== 23.2.2016 =================================== NP-úplnost MAX-2-SAT Algoritmus pro problém batohu polynomiální složitosti ve velikosti vstupních čísel. Aproximační algoritmy: - vrcholové pokrytí s faktorem 2 - TSP s faktorem 3/2 NP-úplnost problému množinového pokrytí =================================== 1.3.2016 =================================== Aproximace množinového pokrytí s faktorem log m, zmínka o analýze téhož algoritmu, která ukazuje, že faktor je H(max_i |S_i|). Polynomiální algoritmus pro 2-SAT pomocí unit propagation, úplnost rezoluční metody. Zavedení PSPACE a důkaz NP \subseteq PSPACE. Zmínka: polynomiální hierarchive je obsažena v PSPACE. Zmíněn důkaz, že pokud je polynomiální hierarchive nekonečná, pak nevyčerpává PSPACE. Zmínka o nedeterministickém prostoru: NSPACE(f) \subseteq NSPACE(f^2).