ФП (сложность)

В теории сложности вычислений класс сложности FP представляет собой набор функциональных задач , которые могут быть решены детерминированной машиной Тьюринга за полиномиальное время . функциональная версия проблемы решения класса P. Это Грубо говоря, это класс функций, которые можно эффективно вычислять на классических компьютерах без рандомизации.

Разница между FP и P заключается в том, что задачи в P имеют однобитовые ответы «да/нет», тогда как задачи в FP могут иметь любой результат, который можно вычислить за полиномиальное время. Например, сложение двух чисел — это задача FP , а определение того, является ли их сумма нечетной, находится в P .

Задачи о функциях с полиномиальным временем имеют основополагающее значение для определения редукций с полиномиальным временем , которые, в свою очередь, используются для определения класса NP-полных задач.

Формальное определение

Формально FP определяется следующим образом:

Бинарное отношение $P(x,y)$ находится в FP тогда и только тогда, когда существует детерминированный алгоритм с полиномиальным временем, который, учитывая $x$, либо находит некоторые $y$ такой, что $P(x,y)$ держится или сигнализирует об отсутствии такого $y$ существует.

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

• FNP — это набор бинарных отношений, для которых существует алгоритм с полиномиальным временем, который по заданным x и y проверяет, выполняется ли P( x , y ). Так же, как P и FP тесно связаны, NP тесно связан с FNP . FP = FNP тогда и только тогда, когда P = NP .
• Поскольку машина, использующая логарифмическое пространство, имеет не более полиномиально много конфигураций, FL , набор функциональных задач, которые можно вычислить в логарифмическом пространстве, содержится в FP . Неизвестно, будет ли FL = FP ; это аналогично проблеме определения того, ли классы решений P и L. равны

Внешние ссылки

• Зоопарк сложности: FP