 | Эта статья требует дополнительных ссылок для проверки . ( август 2018 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон ) |
В теории сложности , UP ( однозначная недетерминирована полиномиального время ) является класс сложности из задач решения разрешим в полиномиальное время на однозначной машине Тьюринга с более чем одним принимающим путем для каждого входа. UP содержит P и содержится в NP .
Обычная переформулировка NP гласит, что язык находится в NP тогда и только тогда, когда данный ответ может быть проверен детерминированной машиной за полиномиальное время. Точно так же язык находится в состоянии UP, если данный ответ может быть проверен за полиномиальное время, а проверяющая машина принимает не более одного ответа для каждого экземпляра проблемы. Более формально язык L принадлежит UP, если существует алгоритм A с полиномиальным временем с двумя входами и константа c такие, что
- если x в L , то существует уникальный сертификат y с таким, что
- если x не находится в L , не существует сертификата y с таким, что
- Алгоритм A проверяет L за полиномиальное время.
UP (и его дополнение co-UP ) содержат как задачу целочисленной факторизации, так и задачу игры на четность ; поскольку решительные усилия еще предстоит найти решение любой из этих проблем за полиномиальное время, предполагается, что трудно показать P = UP или даже P = ( UP ∩ co-UP ).
Теорема Валианта – Вазирани утверждает, что NP содержится в RP Promise-UP , что означает, что существует рандомизированное сокращение любой проблемы в NP до проблемы в Promise-UP .
У UP нет каких-либо полных проблем. [1]
Ссылки [ править ]
Ссылки [ править ]
- Лейн А. Хемаспандра и Йорг Роте, Однозначные вычисления: булевы иерархии и разреженные полные по Тьюрингу множества , SIAM J. Comput., 26 (3) (июнь 1997 г.), 634–653
