Vyčíslitelnost a složitost
11. blok: další NP-úplné problémy, prostorová složitost, vztahy složitostních tříd
Studium
Učivo tohoto bloku je z větší části popsáno v kapitolách 2.1 až 2.2 těchto skript:
Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.
https://is.muni.cz/el/fi/podzim2023/IB107/um/IB107-slozitost-2021.pdf
Problémy VETREX-COVER a SUBSET-SUM jsou výborně popsány v knize Michaela Sipsera Introduction to the theory of computation.
Následují slajdy k jedenáctému bloku, do kterých si můžete dělat poznámky, a dále výuková videa. Pozor: videa nepokrývají problém SUBSET-SUM.