UP (Complexitat)

En teoria de complexitat, la classe de complexitat UP és la classe de problemes de decisió que es poden resoldre en temps polinòmic en una màquina de Turing no ambigua per almenys un camí que accepte per cada entrada.

Una reformulació de la definició de la classe NP s'expressa dient que un llenguatge és a NP si i només si donada una resposta, es pot verificar en un temps polinòmic per una màquina de Turing determinista. De manera similar, un llenguatge és a UP si donada una resposta es pot verificar en un temps polinòmic, i el verificador només accepta com a molt una resposta per cada instància del problema. Més formalment, un llenguatge L pertany a UP si existeix un algorisme de dues entrades i temps polinòmic A i una constant c tal que:

• si x és de L, llavors existeix un únic certificat y amb ${\displaystyle |y|=O(|x|^{c})}$tal que ${\displaystyle A(x,y)=1}$
• si x no és de L, llavors no existeix un certificat y amb ${\displaystyle |y|=O(|x|^{c})}$tal que ${\displaystyle A(x,y)=1}$
• l'algorisme A verifica L en un temps polinòmic

Relació amb d'altres classes

UP conté a la classe P i està continguda dins de NP.

Es coneix que la classe UP conté tots els problemes complets.

La classe NP està dins de la classe RP^UP-promesa, que vol dir que existeix una reducció de qualsevol problema dins de NP cap a un problema a la classe UP-promesa.