Оглавление
FNP (сложность)
-
Определение и свойства FNP
- FNP – это класс бинарных отношений, расширяющий NP.
- FNP не включает недетерминизм и соответствует языку NP.
- Для каждой задачи в NP существует соответствующая FNP-версия, которая задает вопрос о ценности объекта.
-
Сложность и NP-полные задачи
- FNP-версии NP-полных задач являются NP-сложными.
- В 1994 году было показано, что не все FNP-проблемы являются самоустанавливающимися.
-
Задача поиска в FNP
- Задача поиска в FNP заключается в нахождении y, удовлетворяющего P(x, y), или в указании отсутствия такого y.
- Если P = NP, то задача поиска в FNP может быть решена за полиномиальное время.
-
Редукция и связанные классы сложности
- Редукция – это эффективный способ преобразования задач в FNP.
- FP – это набор бинарных отношений с полиномиальным алгоритмом поиска.
- TFNP – это подмножество FNP, содержащее отношения с хотя бы одним y для каждого x.
-
Рекомендации и внешние ссылки
- Статья содержит ссылки на “Зоопарк сложности: FNP”.
Полный текст статьи: