UP (計算複雑性理論)
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/08/17 10:17 UTC 版)
計算複雑性理論において、複雑性クラス UP ("Unambiguous Non-deterministic Polynomial-time") とは、入力に対して高々1つの受容経路を持つ非決定性チューリング機械で多項式時間で解ける決定問題の集合である。UP は Pを包含し、NP に包含される。その際、P ≠ UP または UP ≠ NP(あるいは両方)と考えられている(P≠NP予想)。多くの学者は P とも NP とも等しくないと予想している。
- 1 UP (計算複雑性理論)とは
- 2 UP (計算複雑性理論)の概要
- UP (計算複雑性理論)のページへのリンク