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).