#дневниклекций
Буду стараться писать сюда, что успели пройти на лекциях. Если пропускаю что-то важное, дополняйте. Сегодня было:
- Рассказ о курсе и системе оценивания.
- Неформальное определение P и NP, переборное решение задач из NP
- Примеры похожих друг на друга задач, имеющих разную сложность: раскраска в 2 и 3 цвета, эйлеровость и гамильтоновость, проверки на простоту и на наличие простого делителя в данном диапазоне
- Обсуждение, почему полиномиальность и эффективность это синонимы
- Роль вопроса о P и NP в машинном доказательстве теорем
- 5 миров Импальяццо: возможные статусы решения проблемы и их последствия для общества, в том числе связь с криптографией
- Обнаруженные барьеры к решению проблемы P/NP.

В следующий раз будем изучать временны̀е сложностные классы - детерминированные, недетерминированные и ко-классы.