跳转到内容

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]

參考資料

[编辑]