Сложность вычислительных задач

М. Н. Вялый1

• Содержание
• 1. Вычисление каких функций рассматривается
• 2. Способы решения задач
  • 2.1. Исполнитель
  • 2.2. Машины Тьюринга
• 3. Сложность и сложностные классы
  • 3.1. Сложность вычисления
  • 3.2. Сложность алгоритма
  • 3.3. Сложность задачи
  • 3.4. Почему полиномы?
• 4. Как различать сложные и простые задачи?
  • 4.1. Полиномиальная сводимость
  • 4.2. Класс
• 5. Набросок доказательства теоремы Кука-Левина
• 6. Примеры NP-полных задач
  • 6.1. 3-КНФ
  • 6.2. Разрешимость системы уравнений в поле
  • 6.3. Целочисленное линейное программирование (ЦЛП)
  • 6.4. 3-раскраска
• 7. Класс PSPACE
• 8. Класс IP
  • 8.1. Дополнительные возможности: подбрасывание монетки и класс BPP
  • 8.2. Определение класса IP
  • 8.3.
  • 8.4.
• 9. Заключение
• Список литературы