Введение

Класс сложности
В теории вычислительной сложности класс сложности FNP является расширением функциональной задачи, соответствующей классу задач принятия решений NP. Название несколько вводит в заблуждение, поскольку технически это класс бинарных отношений, а не функций, как объясняет следующее формальное определение:

Бинарное отношение P(x, y), где длина y полиномиально не превышает длину x, принадлежит классу FNP тогда и только тогда, когда существует детерминированный алгоритм с полиномиальным временем работы, который может определить, выполняется ли P(x, y) для заданных x и y. Это определение не включает недетерминизм и аналогично определению проверяющего для NP. Для каждого отношения FNP существует непосредственно соответствующий язык NP, иногда называемый задачей принятия решений, порожденной или соответствующей данному отношению FNP. Этот язык формируется путем выбора всех x, для которых P(x, y) выполняется для некоторого y; однако для конкретной задачи принятия решений может существовать более одного отношения FNP. Многие задачи в NP, включая многие NP-полные задачи, спрашивают, существует ли определенный объект, например, удовлетворяющее присваивание, раскраска графа или клика заданного размера. FNP-версии этих задач спрашивают не только о существовании, но и о значении этого объекта, если он существует. Это означает, что FNP-версия каждой NP-полной задачи является NP-трудной. Белларе и Голдвассер показали в 1994 году, используя некоторые стандартные предположения, что существуют задачи в NP, для которых их FNP-версии не являются самоприводимыми, что подразумевает, что они сложнее, чем их соответствующая задача принятия решений. Для каждого P(x, y) в FNP соответствующая задача поиска состоит в следующем: для заданного x найти y, такое что P(x, y) выполняется, или указать, что такого y не существует. Задача поиска для каждого отношения в FNP может быть решена за полиномиальное время тогда и только тогда, когда P = NP. Этот результат обычно формулируется как "FP = FNP тогда и только тогда, когда P = NP"; однако для истинности этого утверждения необходимо переопределить FP и FNP таким образом, чтобы элементы FP и FNP не были отношениями, а вместо этого представляли собой задачи поиска, связанные с отношениями.

Связанные классы сложности

FP — это множество бинарных отношений, для которых существует алгоритм, работающий за полиномиальное время, который, получив на вход x, находит некоторое y, при котором P(x, y) истинно. Отношение между FNP и FP аналогично отношению между NP и P. TFNP является подмножеством FNP: оно содержит те отношения из FNP, для которых для каждого x существует хотя бы одно y, при котором P(x, y) истинно.