Функциональная проблема
-
Определение и примеры функциональных задач
- Функциональная задача — это вычислительная задача с одним результатом для каждого входа, но более сложным, чем в задаче принятия решения.
- Примеры включают задачу выполнимости булевых формул и задачу о разложении чисел на множители.
-
Связь с другими классами сложности
- Функциональные задачи относятся к классу FNP, который является аналогом NP в классе функций.
- Задачи в FNP могут быть решены за полиномиальное время с помощью оракула, решающего исходную задачу.
- Самовосстанавливаемость — это свойство, при котором задача может быть решена за полиномиальное время с использованием только полиномиального числа вызовов подпрограммы.
-
Сокращения и устранение проблем
- Функциональные проблемы могут быть сведены к другим функциональным проблемам с помощью полиномиальных функций.
- Проблема FSAT является примером задачи, связанной с FNP, и если P = NP, то FP = FNP.
-
Общие функциональные проблемы и TFNP
- Отношение R, используемое для определения функциональных задач, может быть неполным, поэтому рассматриваются полные соотношения.
- TFNP — это класс задач, которые гарантированно имеют решения, и если TFNP содержит проблему с завершением FNP, то NP = co-NP.
-
Рекомендации
- Ссылки на книги для более подробного изучения теории сложности вычислений.
Полный текст статьи: