UP (复杂度)

在计算复杂度理论内，UP（"Unambiguous Non-deterministic Polynomial-time"，非模糊非决定型多项式时间）是一个决定型问题的复杂度类，能以非决定型图灵机在多项式时间内解决，且对任何输入只有至多一条接受的路径。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尚未被找出有任何完全问题（complete problems）。^[1]