ФНП (сложность)
В теории сложности вычислений класс сложности FNP является проблем функциональным расширением принятия решений класса 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 ) возвращает true, то A 1 ( x , g( y )) возвращает true;
- Для всех x : если A 2 ( f ( x ), y ) возвращает false для всех y , то 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 ).
Ссылки [ править ]
- ^ Элейн Рич , Автоматы, вычислимость и сложность: теория и приложения , Прентис Холл, 2008, ISBN 0-13-228806-0 , раздел 28.10 «Задачи классов FP и FNP», стр. 689–694.
- ^ М. Белларе и С. Гольдвассер. Сложность решения против поиска . SIAM Journal on Computing, Vol. 23, № 1, февраль 1994 г.
- ^ Даскалакис, Костис (2015). «22. ППАД» . MIT OpenCourseWare .