FP (сложность) - FP (complexity)

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

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

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

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

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

Бинарное отношение в FP , если и только если существует детерминированный полиномиальный алгоритм времени , что, учитывая , можно найти некоторые такие , что имеет место.

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

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

Рекомендации

внешняя ссылка