UP_(計算複雑性理論)とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > UP_(計算複雑性理論)の意味・解説 

UP (計算複雑性理論)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/08/17 10:17 UTC 版)

計算複雑性理論において、複雑性クラス UP ("Unambiguous Non-deterministic Polynomial-time") とは、入力に対して高々1つの受容経路を持つ非決定性チューリング機械多項式時間で解ける決定問題の集合である。UPPを包含し、NP に包含される。その際、PUP または UPNP(あるいは両方)と考えられている(P≠NP予想)。多くの学者は P とも NP とも等しくないと予想している。

別の定式化として、解の検証が決定性チューリング機械で多項式時間で行える場合にのみ、ある言語が NP に含まれると言える。同様に、ある言語が UP に含まれるとは、解を多項式時間で検証でき、かつその検証機械がそれぞれの具体的問題について高々1つの解のみ受容することである。形式的に表せば、言語 LUP に属するのは、2入力の多項式時間アルゴリズム A と定数 c があって、次が成り立つ場合である(アルゴリズム A は L を多項式時間で検証する)。

L = {x in {0,1}* | ∃! certificate, y with |y| = O(|x|c) such that A(x,y) = 1}



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「UP_(計算複雑性理論)」の関連用語

UP_(計算複雑性理論)のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



UP_(計算複雑性理論)のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのUP (計算複雑性理論) (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS