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

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

Оглавление1 FL (сложность)1.1 Определение класса сложности FL1.2 Отличие от задач принятия решений1.3 Связь с FP и NP1.4 Рекомендации2 ФЛ (сложность) […]

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

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

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

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

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

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

  • Связь с FP и NP

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

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

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

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

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

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

  1. РЛ (сложность) Оглавление1 RL (сложность)1.1 Определение рандомизированного логарифмического пространства (RL)1.2 Особенности вероятностных машин Тьюринга1.3 Отношение к другим классам...
  2. Интеллект принятия решений Оглавление1 Способность принимать решения1.1 Определение и история аналитики принятия решений1.2 Применение и преимущества1.3 Основные принципы и...
  3. Параметризованная сложность Оглавление1 Параметризованная сложность1.1 Определение параметризованной сложности1.2 Примеры параметризованных задач1.3 Иерархия параметризованных задач1.4 Пара-NP и XP1.5 Иерархия...
  4. Проблема принятия решения Оглавление1 Проблема решения1.1 Определение и классификация задач принятия решений1.2 Примеры задач принятия решений1.3 Методы решения задач...
  5. Проблема принятия решения Оглавление1 Проблема решения1.1 Определение и классификация задач принятия решений1.2 Примеры задач принятия решений1.3 Методы решения задач...
  6. Групповое принятие решений Оглавление1 Принятие групповых решений1.1 Основы группового принятия решений1.2 Преимущества и недостатки группового принятия решений1.3 Факторы, влияющие...
  7. ФП (сложность) Оглавление1 FP (сложность)1.1 Определение класса сложности FP1.2 Связь с другими классами сложности1.3 Рекомендации и внешние ссылки2...
  8. Решатель (машина Тьюринга) Оглавление1 Решающий модуль (машина Тьюринга)1.1 Определение и свойства решающих модулей1.2 Неразрешимость определения решающего модуля1.3 Примеры функций,...
  9. РП (сложность) Оглавление1 RP (сложность)1.1 Определение рандомизированного полиномиального времени (RP)1.2 Практическое применение и вероятность ошибок1.3 Формальное определение RP1.4...
  10. Машина с произвольным доступом к хранимой программе Оглавление1 Устройство для запоминания программ с произвольным доступом1.1 Определение и классификация машин Тьюринга1.2 Примеры машин Тьюринга1.3...
  11. Искусственный интеллект Оглавление1 Искусственный интеллект1.1 Искусственный интеллект (ИИ)1.2 Цели и методы ИИ1.3 История и развитие ИИ1.4 Проблемы и...
  12. УП (сложность) Оглавление1 ВВЕРХ (сложность)1.1 Определение UP1.2 Переформулировка NP1.3 Примеры задач в UP1.4 Сложность P=UP и P=(UP ∩...
  13. Сложность Оглавление1 Сложность1.1 Определение сложности1.2 Сложность в различных областях1.3 Теории сложности1.4 Проблемы классификации и сложность задач1.5 Закон...
  14. PSPACE Оглавление1 ПРОСТРАНСТВО1.1 Определение PSPACE1.2 Эквивалентность NPSPACE и PSPACE1.3 Соотношение с другими классами сложности1.4 Примеры задач в...
  15. P (сложность) P (сложность) P – класс задач, решаемых за полиномиальное время.  P содержит множество естественных задач, включая...
  16. НП (сложность) NP (сложность) NP – класс задач, решаемых недетерминированными машинами Тьюринга за полиномиальное время.  NP содержит все...
  17. Динамическое принятие решений Оглавление1 Динамичное принятие решений1.1 Обзор исследований динамического принятия решений1.2 Когнитивные модели1.3 Обучение на основе примеров1.4 Влияние...
  18. Список терминов, относящихся к алгоритмам и структурам данных Оглавление1 Список терминов, относящихся к алгоритмам и структурам данных1.1 Основные понятия и термины в информатике1.2 Классификация...
  19. Средняя сложность Оглавление1 Средняя сложность кейса1.1 Определение и история сложности1.2 Ранние работы и определение1.3 Сложность в среднем и...
  20. ТФНП Оглавление1 ТФНП1.1 Определение и классификация задач1.2 Подклассы TFNP1.3 Примеры задач и их сложность1.4 Связь с NP...
  21. Точное квантово-полиномиальное время Оглавление1 Точное квантовое полиномиальное время1.1 Определение EQP1.2 Первоначальное определение EQP1.3 Амплитуды в EQP1.4 Рекомендации1.5 Полный текст...
  22. СК (сложность) Оглавление1 SC (сложность)1.1 Определение класса SC1.2 Отличие от класса P ∈ PolyL1.3 Примеры задач в классе...

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

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