УП (сложность)

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

Оглавление1 ВВЕРХ (сложность)1.1 Определение UP1.2 Переформулировка NP1.3 Примеры задач в UP1.4 Сложность P=UP и P=(UP ∩ co-UP)1.5 Теорема Валианта-Вазирани1.6 Отсутствие […]

Complexity classes, Классы сложности

ВВЕРХ (сложность)

  • Определение UP

    • UP – это класс задач, решаемых за полиномиальное время на машине Тьюринга с одним принимающим путем. 
    • UP включает в себя P и содержится в NP. 

  • Переформулировка NP

    • Язык находится в NP, если его ответ можно проверить за полиномиальное время детерминированной машиной. 
    • Машина-верификатор принимает не более одного ответа на каждый экземпляр задачи. 

  • Примеры задач в UP

    • UP включает задачи целочисленной факторизации и игры на четность. 

  • Сложность P=UP и P=(UP ∩ co-UP)

    • Пока не найдено решение для этих задач за полиномиальное время, сложно доказать равенство P=UP или P=(UP ∩ co-UP). 

  • Теорема Валианта-Вазирани

    • NP содержится в RPPromise-UP, что означает возможность случайного преобразования любой задачи из NP в задачу из Promise-UP. 

  • Отсутствие серьезных проблем у UP

    • UP не имеет серьезных проблем. 

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

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

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

  1. Теорема Урсеску Оглавление1 Теорема Урсеску1.1 Определение и свойства выпуклых множеств1.2 Теорема о выпуклых множествах1.3 Теорема о пересечении выпуклых...
  2. Поправка о равных правах Оглавление1 Поправка о равных правах1.1 История поправки о равных правах (ERA)1.2 Ранняя история и поддержка1.3 Ратификация...
  3. Гендерное равенство Оглавление1 Гендерное равенство1.1 История феминизма1.2 Основные направления феминизма1.3 Современные феминистские движения1.4 Гендерное равенство1.5 Гендерные исследования1.6 Феминистские...
  4. Социальное равенство Оглавление1 Социальное равенство1.1 Определение социального равенства1.2 Равенство перед законом1.3 Равенство возможностей1.4 Равенство результатов1.5 Информационная этика и...
  5. Параметризованная сложность Оглавление1 Параметризованная сложность1.1 Определение параметризованной сложности1.2 Примеры параметризованных задач1.3 Иерархия параметризованных задач1.4 Пара-NP и XP1.5 Иерархия...
  6. Равенство перед законом Оглавление1 Равенство перед законом1.1 Определение равенства перед законом1.2 Исторический контекст1.3 Развитие равенства перед законом в США1.4...
  7. Сложность Оглавление1 Сложность1.1 Определение сложности1.2 Сложность в различных областях1.3 Теории сложности1.4 Проблемы классификации и сложность задач1.5 Закон...
  8. Список терминов, относящихся к алгоритмам и структурам данных Оглавление1 Список терминов, относящихся к алгоритмам и структурам данных1.1 Основные понятия и термины в информатике1.2 Классификация...
  9. Средняя сложность Оглавление1 Средняя сложность кейса1.1 Определение и история сложности1.2 Ранние работы и определение1.3 Сложность в среднем и...
  10. ТФНП Оглавление1 ТФНП1.1 Определение и классификация задач1.2 Подклассы TFNP1.3 Примеры задач и их сложность1.4 Связь с NP...
  11. РЛ (сложность) Оглавление1 RL (сложность)1.1 Определение рандомизированного логарифмического пространства (RL)1.2 Особенности вероятностных машин Тьюринга1.3 Отношение к другим классам...
  12. P (сложность) Оглавление1 P (сложность)1.1 Определение и свойства класса P1.2 Примеры задач в P1.3 Отношения с другими классами...
  13. СЛЕДУЮЩИЙ ВРЕМЯ Оглавление1 СЛЕДУЮЩИЙ РАЗ1.1 Определение NEXPTIME1.2 Примеры задач в NEXPTIME1.3 Сложность задач в NEXPTIME1.4 Связь с другими...
  14. Феминизм – Arc.Ask3.Ru Оглавление1 Феминизм1.1 История феминизма1.2 Основные направления феминизма1.3 Феминистские движения и организации1.4 Феминистская философия и теория1.5 Феминизм...
  15. Феминизм – Arc.Ask3.Ru Оглавление1 Феминизм1.1 История феминизма1.2 Основные направления феминизма1.3 Феминистские движения и организации1.4 Феминистская философия и теория1.5 Феминизм...
  16. P (сложность) P (сложность) P – класс задач, решаемых за полиномиальное время.  P содержит множество естественных задач, включая...
  17. ФП (сложность) Оглавление1 FP (сложность)1.1 Определение класса сложности FP1.2 Связь с другими классами сложности1.3 Рекомендации и внешние ссылки2...
  18. NP-твердость Оглавление1 NP-твердость1.1 Определение NP-сложности1.2 Невозможность полиномиального решения1.3 Примеры NP-сложных задач1.4 Применение NP-сложных задач1.5 Именование и классификация...
  19. Полиномиальное сокращение времени Оглавление1 Сокращение полиномиального времени1.1 Основы сокращения за полиномиальное время1.2 Типы сокращений за полиномиальное время1.3 Полнота и...
  20. Полиномиальная иерархия Оглавление1 Полиномиальная иерархия1.1 Определение и свойства полиномиальной иерархии1.2 Теоремы о сложности задач1.3 Примеры задач и их...
  21. РП (сложность) Оглавление1 RP (сложность)1.1 Определение рандомизированного полиномиального времени (RP)1.2 Практическое применение и вероятность ошибок1.3 Формальное определение RP1.4...
  22. Теоремы Силова Оглавление1 Теоремы Силова1.1 Теоремы Силова1.2 Определение силовских подгрупп1.3 Теорема Лагранжа1.4 Теорема Силова (1)1.5 Теорема Коши1.6 Теорема...

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