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]

參考資料

1. Complexity Zoo: UP