WikiDer > UP (сложность)

Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: "UP" сложность – Новости · газеты · книги · ученый · JSTOR (Август 2018 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

В теория сложности, ВВЕРХ (однозначное недетерминированное полиномиальное время) это класс сложности из проблемы решения разрешимый в полиномиальное время на однозначная машина Тьюринга с не более чем одним принимающим путем для каждого входа. ВВЕРХ содержит п и содержится в НП.

Общая переформулировка НП заявляет, что язык находится в НП тогда и только тогда, когда данный ответ может быть проверен детерминированной машиной за полиномиальное время. Точно так же язык находится в ВВЕРХ если данный ответ может быть проверен за полиномиальное время, а проверяющая машина принимает не более один ответ на каждый экземпляр проблемы. Более формально язык L принадлежит ВВЕРХ если существует алгоритм с полиномиальным временем с двумя входами А и постоянный c такой, что

если х в L , значит существует уникальный сертификат у с ${ displaystyle | y | = O (| x | ^ {c})}$ такой, что ${ Displaystyle А (х, у) = 1}$

если x не в L, сертификата нет у с ${ displaystyle | y | = O (| x | ^ {c})}$ такой, что ${ Displaystyle А (х, у) = 1}$

алгоритм А проверяет L за полиномиальное время.

ВВЕРХ (и это дополнять совместная работа) содержат как целочисленная факторизация проблема и паритетная игра проблема; поскольку целенаправленные усилия еще не привели к полиномиальному решению любой из этих проблем, предполагается, что будет трудно показать п=ВВЕРХ, или даже п=(ВВЕРХ ∩ совместная работа).

В Теорема Вэлианта – Вазирани утверждает, что НП содержится в RP^{Обещание}, что означает, что есть рандомизированное сокращение от любой проблемы в НП к проблеме в Обещание.

ВВЕРХ не известно, есть ли полный проблемы.^[1]

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

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

• Лейн А. Хемаспандра и Йорг Роте, Однозначные вычисления: булевы иерархии и разреженные полные множества по Тьюрингу, SIAM J. Comput., 26 (3) (июнь 1997), 634–653