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

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

. Обычная переформулировка NP утверждает, что язык находится в NP тогда и только тогда, когда данный ответ может быть проверено детерминированной машиной за полиномиальное время. Точно так же язык находится в UP, если данный ответ может быть проверен за полиномиальное время, а проверяющая машина принимает не более одного ответа для каждого экземпляра проблемы. Более формально, язык L принадлежит UP, если существует алгоритм A с полиномиальным временем с двумя входами и константа c, такая что

, если x в L, то существует уникальный сертификат y с $|\; y\; |\; Знак\; равно\; O\; (|\; x\; |\; c)\; \{\backslash \; displaystyle\; |\; y\; |\; =\; O\; (|\; x\; |\; ^\; \{c\})\}$так, что $A\; (x,\; y)\; =\; 1\; \{\backslash \; displaystyle\; A\; (\; x,\; y)\; =\; 1\}$

если x не находится в L, сертификата y с $|\; y\; |\; Знак\; равно\; O\; (|\; x\; |\; c)\; \{\backslash \; displaystyle\; |\; y\; |\; =\; O\; (|\; x\; |\; ^\; \{c\})\}$так, что $A\; (x,\; y)\; =\; 1\; \{\backslash \; displaystyle\; A\; (\; x,\; y)\; =\; 1\}$

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

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

Теорема Вэлианта – Вазирани утверждает, что NP содержится в RP, что означает, что существует случайное сокращение любой проблемы в НП к проблеме в Promise-UP.

UP, о каких-либо полных проблемах не известно.

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