WikiDer > FP (сложность)

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

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

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

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

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

А бинарное отношение ${ Displaystyle Р (х, у)}$ в FP тогда и только тогда, когда существует детерминированный алгоритм полиномиального времени, который, учитывая ${ displaystyle x}$, могу найти ${ displaystyle y}$ такой, что ${ Displaystyle Р (х, у)}$ держит.

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

Как только п и FP тесно связаны, НП тесно связан с ФНП.

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

использованная литература

• Bürgisser, Питер (2000). Полнота и редукция теории алгебраической сложности. Алгоритмы и вычисления в математике. 7. Берлин: Springer-Verlag. п. 66. ISBN 3-540-66752-0. Zbl 0948.68082.
• Рич, Элейн (2008). «28.10» Задачные классы FP и FNP."". Автоматы, вычислимость и сложность: теория и приложения. Прентис Холл. С. 689–694. ISBN 0-13-228806-0.

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

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