Property |
Value |
dbo:abstract
|
- 計算複雑性理論において、複雑性クラス UP ("Unambiguous Non-deterministic Polynomial-time") とは、入力に対して高々1つの受容経路を持つ非決定性チューリング機械で多項式時間で解ける決定問題の集合である。UP は Pを包含し、NP に包含される。その際、P ≠ UP または UP ≠ NP(あるいは両方)と考えられている(P≠NP予想)。多くの学者は P とも NP とも等しくないと予想している。 別の定式化として、解の検証が決定性チューリング機械で多項式時間で行える場合にのみ、ある言語が NP に含まれると言える。同様に、ある言語が UP に含まれるとは、解を多項式時間で検証でき、かつその検証機械がそれぞれの具体的問題について高々1つの解のみ受容することである。形式的に表せば、言語 L が UP に属するのは、2入力の多項式時間アルゴリズム A と定数 c があって、次が成り立つ場合である(アルゴリズム A は L を多項式時間で検証する)。 L = {x in {0,1}* | ∃! certificate, y with |y| = O(|x|c) such that A(x,y) = 1} (ja)
- 計算複雑性理論において、複雑性クラス UP ("Unambiguous Non-deterministic Polynomial-time") とは、入力に対して高々1つの受容経路を持つ非決定性チューリング機械で多項式時間で解ける決定問題の集合である。UP は Pを包含し、NP に包含される。その際、P ≠ UP または UP ≠ NP(あるいは両方)と考えられている(P≠NP予想)。多くの学者は P とも NP とも等しくないと予想している。 別の定式化として、解の検証が決定性チューリング機械で多項式時間で行える場合にのみ、ある言語が NP に含まれると言える。同様に、ある言語が UP に含まれるとは、解を多項式時間で検証でき、かつその検証機械がそれぞれの具体的問題について高々1つの解のみ受容することである。形式的に表せば、言語 L が UP に属するのは、2入力の多項式時間アルゴリズム A と定数 c があって、次が成り立つ場合である(アルゴリズム A は L を多項式時間で検証する)。 L = {x in {0,1}* | ∃! certificate, y with |y| = O(|x|c) such that A(x,y) = 1} (ja)
|
dbo:wikiPageID
| |
dbo:wikiPageLength
|
- 757 (xsd:nonNegativeInteger)
|
dbo:wikiPageRevisionID
| |
dbo:wikiPageWikiLink
| |
prop-ja:wikiPageUsesTemplate
| |
dct:subject
| |
rdfs:comment
|
- 計算複雑性理論において、複雑性クラス UP ("Unambiguous Non-deterministic Polynomial-time") とは、入力に対して高々1つの受容経路を持つ非決定性チューリング機械で多項式時間で解ける決定問題の集合である。UP は Pを包含し、NP に包含される。その際、P ≠ UP または UP ≠ NP(あるいは両方)と考えられている(P≠NP予想)。多くの学者は P とも NP とも等しくないと予想している。 別の定式化として、解の検証が決定性チューリング機械で多項式時間で行える場合にのみ、ある言語が NP に含まれると言える。同様に、ある言語が UP に含まれるとは、解を多項式時間で検証でき、かつその検証機械がそれぞれの具体的問題について高々1つの解のみ受容することである。形式的に表せば、言語 L が UP に属するのは、2入力の多項式時間アルゴリズム A と定数 c があって、次が成り立つ場合である(アルゴリズム A は L を多項式時間で検証する)。 L = {x in {0,1}* | ∃! certificate, y with |y| = O(|x|c) such that A(x,y) = 1} (ja)
- 計算複雑性理論において、複雑性クラス UP ("Unambiguous Non-deterministic Polynomial-time") とは、入力に対して高々1つの受容経路を持つ非決定性チューリング機械で多項式時間で解ける決定問題の集合である。UP は Pを包含し、NP に包含される。その際、P ≠ UP または UP ≠ NP(あるいは両方)と考えられている(P≠NP予想)。多くの学者は P とも NP とも等しくないと予想している。 別の定式化として、解の検証が決定性チューリング機械で多項式時間で行える場合にのみ、ある言語が NP に含まれると言える。同様に、ある言語が UP に含まれるとは、解を多項式時間で検証でき、かつその検証機械がそれぞれの具体的問題について高々1つの解のみ受容することである。形式的に表せば、言語 L が UP に属するのは、2入力の多項式時間アルゴリズム A と定数 c があって、次が成り立つ場合である(アルゴリズム A は L を多項式時間で検証する)。 L = {x in {0,1}* | ∃! certificate, y with |y| = O(|x|c) such that A(x,y) = 1} (ja)
|
rdfs:label
|
- UP (計算複雑性理論) (ja)
- UP (計算複雑性理論) (ja)
|
owl:sameAs
| |
prov:wasDerivedFrom
| |
foaf:isPrimaryTopicOf
| |
is dbo:wikiPageDisambiguates
of | |
is dbo:wikiPageWikiLink
of | |
is owl:sameAs
of | |
is foaf:primaryTopic
of | |