| Что: | Лекция |
| Когда: | Понедельник, 23 ноября 2020, 18:30–19:50 |
| Где: | Конференция в zoom, Онлайн |
Невычислимость колмогоровской сложности. Теорема Геделя о неполноте в форме Чайтина. Бесконечность простых чисел. Нижняя оценка на сложность распознавания палиндрома одноленточными машинами Тьюринга.
Приближенные алгоритмы для MaxSAT. Вероятностное округление.
Текущая версия конспекта.
