Математическая логика и теория алгоритмов 16. Дополнительная лекция: P=NP

Таймкоды: 0:00 - История вопроса 2:57 - Расшифровка P=NP 4:40 - 2-раскраска и 3-раскраска 10:10 - Эйлеров граф и Гамильтон граф 20:00 - Задача TSP 22:12 - Проверка простоты и разложение на множетели 32:10 - Определение P 34:00 - Определение NP 37:49 - NP вложено в EXP 39:15 - В чем собственно вопрос 40:30 - Почему это интересно математикам 44:10 - Верификация формальных доказательств 46:25 - Что если P=NP? 52:00 - Оборотная сторона равенства 54:27 - Названия других градаций 58:22 - Что известно науке про этот вопрос и почему его не решили 1:00:00 - NP-полные задачи 1:04:17 - Барьер релятивизации 1:07:45 - Барьеры естественных доказательств и алгебризации Дата лекции: 14.05.2025 Лектор: Мусатов Даниил Владимирович Оператор: Алексей Чегодаев Монтажёр: Алексей Чегодаев Плейлист:    • Математическая логика и теория алгоритмов ...