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».
Полный текст статьи: