В теории сложности вычислений , то класс сложности ФНП является функция проблемы продления проблемы решения класса NP . Название несколько неверно, поскольку технически это класс бинарных отношений , а не функций, как объясняет следующее формальное определение:
- Бинарное отношение P ( x , y ), где y не более чем полиномиально длиннее x , находится в FNP тогда и только тогда, когда существует детерминированный алгоритм полиномиального времени, который может определить , выполняется ли P ( x , y ) при заданных x и y. . [1]
Это определение не предполагает недетерминизма и аналогично определению проверяющего NP.
Существует язык NP, непосредственно соответствующий каждому отношению FNP, иногда называемый проблемой принятия решения, вызванной упомянутым отношением FNP или соответствующей ему . Это язык, образованный взятием всех x, для которых выполняется P ( x , y ), для некоторого y ; однако для конкретной задачи решения может быть более одного отношения FNP.
Многие проблемы в NP, включая многие NP-полные проблемы, спрашивают, существует ли конкретный объект, например, удовлетворяющее назначение, раскраска графа или клика определенного размера. Версии этих проблем FNP спрашивают не только, существует ли он, но и какова его ценность, если он существует. Это означает, что FNP-версия каждой NP-полной задачи является NP-сложной . Белларе и Гольдвассер показали в 1994 году, используя некоторые стандартные предположения, что в NP существуют такие проблемы, что их версии FNP не являются самовосстанавливающимися , что означает, что они сложнее, чем соответствующая им проблема принятия решения. [2]
Для каждого P ( x , y ) в FNP проблема поиска, связанная с P ( x , y ), заключается в следующем: по заданному x найти y такое, что P ( x , y ) выполняется, или заявить, что такого y не существует. Задача поиска для каждого отношения в FNP может быть решена за полиномиальное время тогда и только тогда, когда P = NP . Этот результат обычно обозначается как «FP = FNP тогда и только тогда, когда P = NP »; однако, чтобы это утверждение было верным, необходимо переопределить FP и FNP так, чтобы члены FP и FNP не были отношениями, а вместо этого были проблемами поиска, связанными с отношениями.
Скидки
Пусть P 1 и P 2 - две задачи в FNP с соответствующими алгоритмами проверки A 1 , A 2 . Редукция P 1 и P 2 определяется как две эффективно вычислимые функции, f и g , такие, что [3]
- f отображает входы x в P 1 на входы f ( x ) в P 2 ;
- g отображает выходы y в P 2 на выходы g (y) в P 1 ;
- Для всех x и y : если A 2 ( f ( x ), y ) возвращает истину, то A 1 ( x , g ( y )) возвращает истину;
- Для всех x : если A 2 ( f ( x ), y ) возвращает false, то A 1 ( x , g ( y )) возвращает false для всех y .
Связанные классы сложности
- FP - это набор бинарных отношений, для которых существует алгоритм с полиномиальным временем, который по заданному x находит некоторое y, для которого выполняется P ( x , y ). Отношения между FNP и FP аналогичны отношениям между NP и P.
- TFNP - это подмножество FNP: оно содержит те отношения в FNP, для которых для каждого x существует хотя бы один y, для которого выполняется P ( x , y ).
Рекомендации
- ^ Элейн Рич, Автоматы, вычислимость и сложность: теория и приложения , Prentice Hall, 2008, ISBN 0-13-228806-0 , раздел 28.10 «Классы проблем FP и FNP», стр. 689–694
- ^ М. Белларе и С. Гольдвассер. Сложность принятия решения по сравнению с поиском . SIAM Journal on Computing, Vol. 23, No. 1, февраль 1994 г.
- ^ Даскалакис, Костис (2015). «22. PPAD» . MIT OpenCourseWare .