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

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

ВВЕРХ (сложность) Определение UP UP — это класс задач, решаемых за полиномиальное время на машине Тьюринга с одним принимающим путем.  […]

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. Социальное равенство Социальное равенство Определение социального равенства Социальное равенство — это концепция, согласно которой все люди имеют равные...
  2. Параметризованная сложность Параметризованная сложность Определение параметризованной сложности Параметризованная сложность — это класс задач, которые могут быть решены за...
  3. Сложность Сложность Определение сложности Сложность — это свойство системы, которое затрудняет ее понимание и контроль.  Сложность может...
  4. Средняя сложность Средняя сложность кейса Определение и история сложности Сложность в среднем случае — это среднее время выполнения...
  5. Список терминов, относящихся к алгоритмам и структурам данных Список терминов, относящихся к алгоритмам и структурам данных Основные понятия и термины в информатике Алгоритм: последовательность...
  6. ТФНП ТФНП Определение и классификация задач TFNP — это класс задач, которые не могут быть решены за...
  7. РЛ (сложность) RL (сложность) Определение рандомизированного логарифмического пространства (RL) RL — это класс задач, решаемых в логарифмическом пространстве...
  8. СЛЕДУЮЩИЙ ВРЕМЯ СЛЕДУЮЩИЙ РАЗ Определение NEXPTIME NEXPTIME — это класс задач, которые могут быть решены за полиномиальное время...
  9. P (сложность) P (сложность) Определение и свойства класса P P — это класс задач, которые могут быть решены...
  10. P (сложность) P (сложность) P — класс задач, решаемых за полиномиальное время.  P содержит множество естественных задач, включая...
  11. ФП (сложность) FP (сложность) Определение класса сложности FP FP — это набор задач, решаемых детерминированной машиной Тьюринга за...
  12. NP-твердость NP-твердость Определение NP-сложности NP-сложная задача — это задача, для которой существует полиномиальное сокращение от любой задачи...
  13. Полиномиальное сокращение времени Сокращение полиномиального времени Основы сокращения за полиномиальное время Сокращение за полиномиальное время позволяет решать одну задачу...
  14. Полиномиальная иерархия Полиномиальная иерархия Определение и свойства полиномиальной иерархии Полиномиальная иерархия — это иерархия сложности задач, где каждая...

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

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