Всё, что Вы хотели бы знать вычислениях и их сложности
В этом учебном году я впервые читаю открытый годовой курс о вычислениях. Курс будет посвящен вычислимости, сложности вычислений и теоретическим основам криптографии. Первая часть курса называется "Основы вычислимости и теории сложности", первая лекция состоится в среду 12-го сентября в 18-30 в Мраморном зале ПОМИ РАН, вход свободный. Этот курс будет читаться в рамках Computer Science центра и клуба одновременно. От слушателей курса не предполагается никаких предварительных знаний кроме базовых математических (элементарной комбинаторики, основ математического анализа, алгебры и со второго семестра основ теории вероятностей).
Страница курса на сайте CS-клуба с другим описанием.
Будет не всегда просто, но понятно и очень интересно!
Под катом список тем курса на год.
Часть 1. Основы вычислимости и теории сложности
Разделение на лекции условное!
1) Вычислимые функции, разрешимые множества, определения перечислимого множества. Теорема Поста. Перечислимые множества как проекции разрешимых. Вычислимость функции и перечислимость ее графика. Универсальная функция. Вычислимая функция, которую нельзя доопределить до всюду определенной. Пример перечислимого, но неразрешимого множества.
2) m-сведения, другие примеры неразрешимых множеств. Последовательность Шпеккера. Теорема Успенского-Райса. Теорема Клини о неподвижной точке. Программа, печатающая свой текст. Доказательство теоремы Клини для искуcственного языка программирования. Главные универсальные функции. Вывод теоремы Успенского-Райса из теоремы Клини.
3) Машины Тьюринга. Неразрешимость проблемы равенства слов в полугруппе (выводимости в одностороннем и двустороннем ассоциативном исчислении). Предикатные формулы (формулы I-го порядка). Интерпретации.
4) Выразимость в арифметике. Арифметичность графика вычислимой функции. Арифметическая иерархия. Универсальные множества в арифметической иерархии. Строгость арифметической иерархии. Теоремы Тарского и Геделя. Прямое доказательство теоремы Геделя о неполноте.
5) Колмогоровская сложность относительно декомпрессора, оптимальный декомпрессор. Простейшие свойства колмогоровской сложности. Невычислимость неограниченной нижней оценки на колмогоровскую сложность. Доказательство Чайтина теоремы Геделя о неполноте. Нижняя оценка на сложность копирования слова на одноленточной машине Тьюринга. Доказательство бесконечности простых чисел с помощью колмогоровской сложности. Моделирование k-ленточной машины Тьюринга на двухлентночтной.
6) Недетерминированные машины Тьюринга. Определения класса NP. Примеры. Сведения по Карпу. Понятние полноты. Полнота задачи об ограниченной остановке. Полнота задачи SAT и 3-SAT.
7) NP-задачи поиска. Сведения по Куку. Сведение задач поиска к задачам распознавания. Оптимальный алгоритм для NP-задач поиска. Теорема Ладнера о не NP-полном языке в классе NP.
8) Классы с оракулами. Существование оракулов A и B, при которых P^A = NP^A и P^B не равняете NP^B.
Теоремы об иерархии по времени для детерминированных и недетерминированных вычислений.
9) Вычисления с ограничением по памяти. Теорема Савича и следствие о NPSPACE = PSPACE. Полнота TQBF в классе PSPACE. Логарифмические по памяти сведения и их свойства. Класс NL, полная задача в нем. Замкнутость классов NSpace[s(n)] относительно дополнения.
10) Полиномиальная иерархия. Простейшие свойства, полные задачи в \Sigma_i^P и в \Pi_i^P. Оракульное определение полиномиальной иерархии. Альтернирующие машины Тьюринга и полиномиальная иерархия.
11) Вычисления с ограничением по времени и по памяти. Нижняя оценка для SAT. Булевы схемы. Вычисления с подсказкой. Класс P/poly. Включение P в P/poly. Существование функций большой схемной сложности.
12) Теорема Карпа-Липтона. Языки большой схемной сложности в полиномиальной иерархии (теорема Каннана).
Равномерные схемы. Классы NCi. P-полные задачи. Соотношение между NC1; L;NL и NC2. Замкнутость NC относительно логарифмических по памяти сведений. Эффективные параллельные схемы для сложения и умножения чисел.
Часть 2 Сложность вычислений и основы криптографии (весенний семестр)
Курс является продолжением курса "Основы вычислимости и теории сложности" и посвящен следующем темам: сложность вероятностных алгоритмов, интерактивные системы доказательств, считающие классы, вероятностно проверяемые доказательства, односторонние функции, генераторы псевдослучайных чисел, протоколы с открытым и публичным ключом, привязка к биту, доказательства с нулевым разглашением.
1) Вероятностная машина Тьюринга. Классы BPP и RP. Лемма Шварца-Зиппеля и вероятностный тест равенства двух многочленов. Понижение ошибки в классе BPP, BPP содержится в P/poly, BPP содержится в \Sigma_2.
2) Интерактивные протоколы. Примеры: интерактивный протокол для неизоморфизма графов и для квадратичных невычетов. Теорема Шамира (IP = PSPACE) и ее следствия.
3) Универсальное семейство попарно независимых хеш-функций. Конструкция.. Протокол для нижней
оценки на размер множества. Открытые и закрытые случайные биты,игры Мерлина и Артура. GNI содержится в AM. Теорема Голдвассера-Сипсера (без доказательства).
4) Классы UP и P. Лемма Вэлианта-Вазирани. И ее \oplus-версия. Операции с числом выполняющих наборов и следствия из них. \oplus-версия леммы Вэлианта-Вазирани для полиномиальной иерархии.
5) Классы \sharp P и PP. Теорема Тода. P^{PP} = P^{\sharp P}. Теорема Вэлианта о \sharp-P -полноте 0/1 перманента (без доказаьельства). Интерактивное доказательство для перманента. Следствие об интерактивном доказательстве для P^PP. Включение MA в PP. Схемная сложность PP.
6) Приближенные алгоритмы для задачи MAXSAT и минимальном вершинном покрытии. Вероятностно проверяемые доказательства. Формулировка PCP-теоремы. Эквивалентные формулировки. Неаппроксимируемость MAX-3-SAT.
Код Уолша-Адамара и его локальное декодирование. NP содержится в PCP(poly; 1).
7) Базис Фурье для булевых функций. Тестирование функции на линейность. Сильные и слабые односторонние функции.
8) Примеры предположительно односторонних функций. Односторонние функции с доступным распределением на входах. Универсальная односторонняя функция. Трудный бит и его существование с помощью вероятностного декодирования списком кодов Адамара. Вероятностное декодирование списком кодов Адамара.
9) Вычислительная неразличимость. Односторонняя функция из генератора псевдослучайных чисел. Односторонние перестановки, примеры. Конструкция (n + 1)-генератора на основе перестановки. Конструкция p(n)-генератора.
10) Семейство псевдослучайных функций. Одноразовый и многоразовые протоколы с секретным ключом.
Протокол с открытым ключом. Семейства односторонних перестановок с секретом, примеры.
11) Интерактивный протокол привязки к биту.
Стратегии, разглашающие только f(x). Разглашение при многократном применении стратегии. Интерактивные доказательства с нулевым разглашением. Протокол для изоморфизма графов.
12) Протокол с нулевым разглашением для языка из NP.
Страница курса на сайте CS-клуба с другим описанием.
Будет не всегда просто, но понятно и очень интересно!
Под катом список тем курса на год.
Часть 1. Основы вычислимости и теории сложности
Разделение на лекции условное!
1) Вычислимые функции, разрешимые множества, определения перечислимого множества. Теорема Поста. Перечислимые множества как проекции разрешимых. Вычислимость функции и перечислимость ее графика. Универсальная функция. Вычислимая функция, которую нельзя доопределить до всюду определенной. Пример перечислимого, но неразрешимого множества.
2) m-сведения, другие примеры неразрешимых множеств. Последовательность Шпеккера. Теорема Успенского-Райса. Теорема Клини о неподвижной точке. Программа, печатающая свой текст. Доказательство теоремы Клини для искуcственного языка программирования. Главные универсальные функции. Вывод теоремы Успенского-Райса из теоремы Клини.
3) Машины Тьюринга. Неразрешимость проблемы равенства слов в полугруппе (выводимости в одностороннем и двустороннем ассоциативном исчислении). Предикатные формулы (формулы I-го порядка). Интерпретации.
4) Выразимость в арифметике. Арифметичность графика вычислимой функции. Арифметическая иерархия. Универсальные множества в арифметической иерархии. Строгость арифметической иерархии. Теоремы Тарского и Геделя. Прямое доказательство теоремы Геделя о неполноте.
5) Колмогоровская сложность относительно декомпрессора, оптимальный декомпрессор. Простейшие свойства колмогоровской сложности. Невычислимость неограниченной нижней оценки на колмогоровскую сложность. Доказательство Чайтина теоремы Геделя о неполноте. Нижняя оценка на сложность копирования слова на одноленточной машине Тьюринга. Доказательство бесконечности простых чисел с помощью колмогоровской сложности. Моделирование k-ленточной машины Тьюринга на двухлентночтной.
6) Недетерминированные машины Тьюринга. Определения класса NP. Примеры. Сведения по Карпу. Понятние полноты. Полнота задачи об ограниченной остановке. Полнота задачи SAT и 3-SAT.
7) NP-задачи поиска. Сведения по Куку. Сведение задач поиска к задачам распознавания. Оптимальный алгоритм для NP-задач поиска. Теорема Ладнера о не NP-полном языке в классе NP.
8) Классы с оракулами. Существование оракулов A и B, при которых P^A = NP^A и P^B не равняете NP^B.
Теоремы об иерархии по времени для детерминированных и недетерминированных вычислений.
9) Вычисления с ограничением по памяти. Теорема Савича и следствие о NPSPACE = PSPACE. Полнота TQBF в классе PSPACE. Логарифмические по памяти сведения и их свойства. Класс NL, полная задача в нем. Замкнутость классов NSpace[s(n)] относительно дополнения.
10) Полиномиальная иерархия. Простейшие свойства, полные задачи в \Sigma_i^P и в \Pi_i^P. Оракульное определение полиномиальной иерархии. Альтернирующие машины Тьюринга и полиномиальная иерархия.
11) Вычисления с ограничением по времени и по памяти. Нижняя оценка для SAT. Булевы схемы. Вычисления с подсказкой. Класс P/poly. Включение P в P/poly. Существование функций большой схемной сложности.
12) Теорема Карпа-Липтона. Языки большой схемной сложности в полиномиальной иерархии (теорема Каннана).
Равномерные схемы. Классы NCi. P-полные задачи. Соотношение между NC1; L;NL и NC2. Замкнутость NC относительно логарифмических по памяти сведений. Эффективные параллельные схемы для сложения и умножения чисел.
Часть 2 Сложность вычислений и основы криптографии (весенний семестр)
Курс является продолжением курса "Основы вычислимости и теории сложности" и посвящен следующем темам: сложность вероятностных алгоритмов, интерактивные системы доказательств, считающие классы, вероятностно проверяемые доказательства, односторонние функции, генераторы псевдослучайных чисел, протоколы с открытым и публичным ключом, привязка к биту, доказательства с нулевым разглашением.
1) Вероятностная машина Тьюринга. Классы BPP и RP. Лемма Шварца-Зиппеля и вероятностный тест равенства двух многочленов. Понижение ошибки в классе BPP, BPP содержится в P/poly, BPP содержится в \Sigma_2.
2) Интерактивные протоколы. Примеры: интерактивный протокол для неизоморфизма графов и для квадратичных невычетов. Теорема Шамира (IP = PSPACE) и ее следствия.
3) Универсальное семейство попарно независимых хеш-функций. Конструкция.. Протокол для нижней
оценки на размер множества. Открытые и закрытые случайные биты,игры Мерлина и Артура. GNI содержится в AM. Теорема Голдвассера-Сипсера (без доказательства).
4) Классы UP и P. Лемма Вэлианта-Вазирани. И ее \oplus-версия. Операции с числом выполняющих наборов и следствия из них. \oplus-версия леммы Вэлианта-Вазирани для полиномиальной иерархии.
5) Классы \sharp P и PP. Теорема Тода. P^{PP} = P^{\sharp P}. Теорема Вэлианта о \sharp-P -полноте 0/1 перманента (без доказаьельства). Интерактивное доказательство для перманента. Следствие об интерактивном доказательстве для P^PP. Включение MA в PP. Схемная сложность PP.
6) Приближенные алгоритмы для задачи MAXSAT и минимальном вершинном покрытии. Вероятностно проверяемые доказательства. Формулировка PCP-теоремы. Эквивалентные формулировки. Неаппроксимируемость MAX-3-SAT.
Код Уолша-Адамара и его локальное декодирование. NP содержится в PCP(poly; 1).
7) Базис Фурье для булевых функций. Тестирование функции на линейность. Сильные и слабые односторонние функции.
8) Примеры предположительно односторонних функций. Односторонние функции с доступным распределением на входах. Универсальная односторонняя функция. Трудный бит и его существование с помощью вероятностного декодирования списком кодов Адамара. Вероятностное декодирование списком кодов Адамара.
9) Вычислительная неразличимость. Односторонняя функция из генератора псевдослучайных чисел. Односторонние перестановки, примеры. Конструкция (n + 1)-генератора на основе перестановки. Конструкция p(n)-генератора.
10) Семейство псевдослучайных функций. Одноразовый и многоразовые протоколы с секретным ключом.
Протокол с открытым ключом. Семейства односторонних перестановок с секретом, примеры.
11) Интерактивный протокол привязки к биту.
Стратегии, разглашающие только f(x). Разглашение при многократном применении стратегии. Интерактивные доказательства с нулевым разглашением. Протокол для изоморфизма графов.
12) Протокол с нулевым разглашением для языка из NP.