ТФНП
-
Определение и классификация задач
- TFNP — это класс задач, которые не могут быть решены за полиномиальное время, но могут быть решены за экспоненциальное время.
- Задачи в TFNP включают в себя задачи, которые не могут быть решены за полиномиальное время даже с помощью вероятностного алгоритма.
-
Подклассы TFNP
- TFNP включает в себя подклассы, такие как PLS, PPA, PPP, PPAD, CLS, EOPL, UEOPL, fp, и другие.
- Каждый подкласс определяется математической теоремой, гарантирующей решение задач.
-
Примеры задач и их сложность
- Задачи в PLS включают поиск локального оптимума для функций.
- Задачи в PPA гарантируют решение с помощью леммы о четности.
- Задачи в PPP решаются с помощью принципа упорядочения.
- Задачи в PPAD требуют завершения строки и могут быть решены за полиномиальное время.
- CLS — это класс задач для непрерывного локального поиска.
- EOPL и UEOPL решают задачи поиска с экспоненциально длинными строками и уникальными решениями.
- fp — это класс задач, которые могут быть решены детерминированно за полиномиальное время.
-
Связь с NP и coNP
- Предполагается, что TFNP не равен NP, но может быть равен FP.
- Если TFNP равен FP, то это означает, что P равен NP ∩ coNP.
Полный текст статьи: