Сокращение полиномиального времени
-
Основы сокращения за полиномиальное время
- Сокращение за полиномиальное время позволяет решать одну задачу с помощью другой.
- Если существует эффективный алгоритм для решения второй задачи, то он применим и к первой.
- Если нет эффективного алгоритма для первой задачи, то и для второй его нет.
-
Типы сокращений за полиномиальное время
- Многократное сокращение: преобразование задачи A в задачу B с сохранением результата.
- Сокращение по таблице истинности: преобразование таблицы истинности для задачи A в таблицу истинности для задачи B.
- Сокращение Тьюринга: решение задачи A с использованием полиномиального числа вызовов подпрограммы для задачи B.
-
Полнота и определение классов сложности
- Полная задача для класса сложности C — это задача P, которую можно свести к C за полиномиальное время.
- Для классов сложности в пределах P используются более слабые сокращения.
- Некоторые классы сложности могут быть определены через многоточечные сокращения.
-
Примеры и определения классов сложности
- Пример класса сложности
- ∃
- R
- {\displaystyle \exists \mathbb {R} }
- , который является NP-сложным, но не полным для NP.
- Класс сложности GI состоит из задач, сводимых к задаче изоморфизма графов, которая является GI-полной.
Полный текст статьи: