Невычислимость колмогоровской сложности. Теорема Геделя о неполноте в форме Чайтина. Бесконечность простых чисел. Нижняя оценка на сложность распознавания палиндрома одноленточными машинами Тьюринга.

Приближенные алгоритмы для MaxSAT. Вероятностное округление.

Текущая версия конспекта.