City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Лекция 11. Колмогоровская сложность (продолжение). Приближенные алгоритмы для MaxSAT
Introduction to Theoretical Computer Science

What: Lecture
When: Monday, 23 November 2020, 22:30–23:50
Where: Конференция в zoom, Онлайн

Description

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

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

Video

Other materials

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