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

От / / Оставьте комментарий

FL (сложность) Определение класса сложности FL FL — это набор задач, решаемых детерминированной машиной Тьюринга в логарифмическом объеме памяти.  Машина […]

Complexity classes, Functions and mappings, Theoretical computer science stubs, Заготовки по теоретической информатике, Классы сложности, Функции и отображения

FL (сложность)

  • Определение класса сложности FL

    • FL — это набор задач, решаемых детерминированной машиной Тьюринга в логарифмическом объеме памяти. 
    • Машина Тьюринга считывает данные с ленты только для чтения и записывает результаты на ленту только для записи. 
    • Ограничение логарифмического пространства относится только к рабочей ленте. 

  • Отличие от задач принятия решений

    • Функциональные задачи выдают сложные выходные данные, в отличие от задач принятия решений, которые выдают только «Да» или «Нет». 

  • Связь с FP и NP

    • FL является подмножеством FP, набора задач, решаемых за детерминированное полиномиальное время. 
    • В FL входят задачи, такие как арифметика с числами, включая сложение, вычитание и умножение, но деление остается сложной проблемой. 

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

    • Статья является теоретической и требует расширения для Википедии. 

Полный текст статьи:

ФЛ (сложность) — Википедия

Похожие статьи:

  1. Интеллект принятия решений Способность принимать решения Определение и история аналитики принятия решений Аналитика принятия решений — это междисциплинарная область,...
  2. РЛ (сложность) RL (сложность) Определение рандомизированного логарифмического пространства (RL) RL — это класс задач, решаемых в логарифмическом пространстве...
  3. Параметризованная сложность Параметризованная сложность Определение параметризованной сложности Параметризованная сложность — это класс задач, которые могут быть решены за...
  4. ФП (сложность) FP (сложность) Определение класса сложности FP FP — это набор задач, решаемых детерминированной машиной Тьюринга за...
  5. Решатель (машина Тьюринга) Решающий модуль (машина Тьюринга) Определение и свойства решающих модулей Решающий модуль — это машина Тьюринга, которая...
  6. РП (сложность) RP (сложность) Определение рандомизированного полиномиального времени (RP) RP — это класс задач, решаемых вероятностной машиной Тьюринга...
  7. Машина с произвольным доступом к хранимой программе Устройство для запоминания программ с произвольным доступом Определение и классификация машин Тьюринга Машины Тьюринга — это...
  8. Сложность Сложность Определение сложности Сложность — это свойство системы, которое затрудняет ее понимание и контроль.  Сложность может...
  9. УП (сложность) ВВЕРХ (сложность) Определение UP UP — это класс задач, решаемых за полиномиальное время на машине Тьюринга...
  10. P (сложность) P (сложность) P — класс задач, решаемых за полиномиальное время.  P содержит множество естественных задач, включая...
  11. PSPACE ПРОСТРАНСТВО Определение PSPACE PSPACE — это класс задач, решаемых машиной Тьюринга за полиномиальное время с использованием...
  12. Анализ решений Анализ принимаемых решений Анализ принятия решений — дисциплина, включающая философию, методологию и практику для формального принятия...
  13. НП (сложность) NP (сложность) NP — класс задач, решаемых недетерминированными машинами Тьюринга за полиномиальное время.  NP содержит все...
  14. Средняя сложность Средняя сложность кейса Определение и история сложности Сложность в среднем случае — это среднее время выполнения...
  15. Список терминов, относящихся к алгоритмам и структурам данных Список терминов, относящихся к алгоритмам и структурам данных Основные понятия и термины в информатике Алгоритм: последовательность...
  16. ТФНП ТФНП Определение и классификация задач TFNP — это класс задач, которые не могут быть решены за...
  17. Проблема принятия решения Проблема решения Задачи принятия решений связаны с выбором правильного ответа на входные данные.  Разрешимость задачи принятия...
  18. Теория принятия решений Теория принятия решений Теория принятия решений — область исследований, изучающая процесс принятия решений и его влияние...

Оставьте комментарий

Прокрутить вверх