ИЗБРАННЫЕ ВОПРОСЫ ТЕОРИИ СЛОЖНОСТИ ВЫЧИСЛЕНИЙ

проф.

1 год

1. Схемы в полном базисе, оценка , класс P/poly, теорема Сэйведжа.

2. Проблема P=?NP и теорема Карпа-Липтона.

3. Верхние оценки для размера и глубины схем, вычисляющих конкретные функции:

    а) PARITY, , . б) Сложение натуральных чисел, , . в) MAJORITY, , . г) Умножение натуральных чисел: , .

4. Экспоненциальная нижняя оценка для сложности неявных булевых функций. Линейная нижняя оценка для пороговой функции .

5. Формулы.

    а) Теорема Spira-Храпченко о связи размера формулы и глубины схемы. б) Лемма Субботовской. в) Нижняя оценка формульной сложности функции Андреева в стандартном базисе. г) Теорема Нечипорука-Патерсона-Цвика. д) Нижняя оценка для функции различения и функции Андреева в полном базисе. е) Теорема Храпченко и нижняя оценка формульной сложности функций PARITY, MAJORITY. ж) Теорема Карчмера-Вигдерсона.

6. Схемы ограниченной глубины.

    а) построение оракулов, относительно которых P=NP и P≠NP: теорема Бейкера, Гилла и Соловея. б) сведение проблемы оракульного отделения PSPACE от PH и от к получению нижних оценок для схем ограниченной глубины. в) Лемма Хостада. г) Экспоненциальная нижняя оценка размера схемы глубины d, вычисляющей функции PARITY, MAJORITY.

7. Монотонные схемы: теорема Разборова о нижней оценке сложности функции КЛИКА.

8. Ветвящиеся программы, контактно-вентильные схемы, связь со сложностью вычислений на машинах Тьюринга.

9. Деревья разрешения.

    а) NPсс со – NPсс = Pсс. б) Пример функции с полиномиальным разрывом вероятностной и детерминированной сложностей. в)BPPdt = Pdt.

10. Коммуникационная сложность.

    а) NPсс со – NPсс = Pсс. б) Быстрый вероятностный алгоритм распознавания отношения равенства. в) Нижняя оценка детерминированной сложности отношения равенства.

11. Интерактивные доказательства.

    а) Определение. б) PSPACEIP. в) MIP=OP. г) NEXP=OP (включение слева направо – без доказательства).

Литература

1. Boppana R. B., Sipser M. The complexity of finite functions.  In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, vol. 1. Algorithms and Complexity, chapter 14, p. 758-804. Elsevier Science Publishers B. V., 1990.