计算复杂度理论内,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]

参考资料

编辑