UP (complexidade)

Na teoria da complexidade, UP ("Tempo Polinomial Não-determinístico Não-ambíguo") é a classe de complexidade dos problemas de decisão resolvidos em tempo polinomial em uma máquina de Turing não ambígua com, no máximo, uma caminho de aceitação para cada entrada. UP contém P e está contida em NP.

Uma reformulação costumeira de NP afirma que uma linguagem está em NP se e somente se uma determinada resposta pode ser verificada por uma máquina determinística em tempo polinomial. Da mesma forma, uma linguagem está em UP, se uma dada resposta pode ser verificada em tempo polinomial, e a máquina verificadora só aceita no máximo uma resposta para cada instância do problema. Mais formalmente, uma linguagem L pertence a UP se existe um algoritmo de tempo polinomial A de duas entradas e uma constante c tal que

se x está em L , então existe um único certificado y com $|y|=O(|x|^{c})$ de tal forma que $A(x,y)=1$

se x não está em L, não há nenhum certificado de y com $|y|=O(|x|^{c})$ de tal forma que $A(x,y)=1$

o algoritmo A verifica L em tempo polinomial.

UP (e seu complemento co-UP) contêm os problemas de fatoração de inteiros e do jogo de paridade; em razão do fato de que determinado esforço ainda tem que ser feito para encontrar uma solução em tempo-polinômial para qualquer um desses problemas, suspeita-se ser difícil mostrar que P=UP, ou mesmo P=(UP ∩ co-UP).

O Teorema de Valiant-Vazirani  afirma que NP está contida em RP^Promise-UP, o que significa que há uma redução aleatorizada de qualquer problema em NP para um problema em Promise-UP.

Não se sabe se UP tem algum problema completo.

Bibliografia

Lane A. HEMASPAANDRA e Jorg Rothe, Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets, SIAM J. Transf., 26(3), 634-653