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

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

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

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

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

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

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

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

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

Ссылки

Источники

• Хемаспаандра, Лейн А.; Роте, Йорг (июнь 1997 г.). «Однозначные вычисления: логические иерархии и разреженные полные множества по Тьюрингу» . SIAM Journal по вычислительной технике . 26 (3): 634–653. arXiv : cs/9907033 . дои : 10.1137/S0097539794261970 . ISSN   0097-5397 .