ФЛ (сложность)
В теории сложности вычислений класс сложности FL представляет собой набор функциональных задач , которые могут быть решены детерминированной машиной Тьюринга в логарифмическом объеме памяти . [1] Как и в определении L , машина считывает входные данные с ленты, доступной только для чтения, и записывает выходные данные на ленту, доступную только для записи; ограничение логарифмического пространства применяется только к рабочей ленте чтения/записи.
Грубо говоря, функциональная задача принимает сложные входные данные и выдает (возможно, столь же сложный) результат. Функциональные проблемы отличаются от проблем принятия решений , которые дают только ответы «Да» или «Нет», и соответствуют множеству проблем L принятия решений , которые могут быть решены в детерминированном лог-пространстве. FL — это подмножество FP , набора функциональных задач, которые можно решить за детерминированное полиномиальное время . [1]
FL Известно, что содержит несколько естественных задач, включая арифметику чисел. Сложение, вычитание и умножение двух чисел довольно просто, но разделение — гораздо более глубокая проблема, которая была открыта на протяжении десятилетий. [2] [3]
Аналогичным образом можно определить FNL , который имеет такое же отношение к NL, как FNP к NP . [1]
Ссылки [ править ]
- ^ Jump up to: а б с Альварес, Карме; Балькасар, Хосе Л.; Дженнер, Биргит (1991), «Функциональные запросы оракула как мера параллельного времени», STACS 91 , Конспекты лекций по информатике, том. 480, Springer, стр. 422–433, doi : 10.1007/BFb0020817 , hdl : 2117/327984 .
- ^ Чиу, А.; Давида, Г.; Литов, Б. (2001), «Деление в логарифмическом пространстве-равномерном NC1», RAIRO Theoretical Informatics and Applications , 35 : 259–276 .
- ^ Аллендер, Эрик (2004), «Прорывы в разделении» (PDF) , Текущие тенденции в теоретической информатике , World Scientific, стр. 147–164 .