В теории сложности вычислений , то класс сложности FP есть множество проблем функций , которые могут быть решены с помощью детерминированной машины Тьюринга в полиномиальное время . Это проблема версия функции решения проблем класса P . Грубо говоря, это класс функций, которые можно эффективно вычислить на классических компьютерах без рандомизации.
Разница между FP и P заключается в том, что проблемы в P имеют однобитовые ответы, да / нет, тогда как проблемы в FP могут иметь любой результат, который может быть вычислен за полиномиальное время. Например, сложение двух чисел является ФП проблема, при определении , если их сумма нечетна в P . [1]
Задачи функций с полиномиальным временем являются фундаментальными для определения редукций с полиномиальным временем , которые, в свою очередь, используются для определения класса NP-полных задач. [2]
Формальное определение
Формально FP определяется следующим образом:
- Бинарное отношениенаходится в FP тогда и только тогда, когда существует детерминированный алгоритм полиномиального времени, который, учитывая , могу найти такой, что держит.
Связанные классы сложности
- FNP - это набор бинарных отношений, для которых существует алгоритм с полиномиальным временем, который по заданным x и y проверяет,выполняетсяли P ( x , y ). Так же, как P и FP тесно связаны, NP тесно связана с FNP . FP = FNP тогда и только тогда, когда P = NP .
- Поскольку машина, использующая логарифмическое пространство, имеет не более полиномиально много конфигураций, FL , набор функциональных задач, которые могут быть вычислены в пространстве журналов, содержится в FP . Неизвестно, является ли FL = FP ; это аналогично проблеме определения того , равны ли классы принятия решений P и L.
Рекомендации
- ^ Bürgisser, Питер (2000). Полнота и редукция теории алгебраической сложности . Алгоритмы и вычисления в математике. 7 . Берлин: Springer-Verlag . п. 66. ISBN 3-540-66752-0. Zbl 0948.68082 .
- ^ Рич, Элейн (2008). «28.10« Проблемы классов ФП и ФНП » ». Автоматы, вычислимость и сложность: теория и приложения . Прентис Холл. С. 689–694. ISBN 0-13-228806-0.