Избранные вопросы теории сложности вычислений



Дата20.07.2016
өлшемі331 Kb.
ИЗБРАННЫЕ ВОПРОСЫ ТЕОРИИ СЛОЖНОСТИ ВЫЧИСЛЕНИЙ

проф. Н. К. Верещагин

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.
Каталог: content root -> programs -> kaf -> special -> logica
special -> Маломерная топология
special -> Устойчивость движения
special -> А. А. Тужилин 1 год, 2-5 курс, аспиранты в курсе излагаются основы новой теории, возникшей на стыке вариационного исчисления, теории графов и геометрии. Классическая вариационная задача
special -> Анализа и обработки социологической информации доц. А. В. Козина 1/2 год
special -> A. M. Райгородский 1 год, 1-2 курс 1 семестр. Геометрические и аналитические методы. Введение. Основные задачи комбинаторной геометрии: проблема (гипотеза) Борсука, проблема Хадвигера-Гохберга-Маркуса-Болтянского
special -> Наследственная механика


Достарыңызбен бөлісу:




©www.dereksiz.org 2020
әкімшілігінің қараңыз

    Басты бет