| dbo:abstract
|
- في علم التعقيد الحسابي القسم UP هو قسم كل المسائل التي يمكن تقريرها بوقت كثير الحدود على آلة تيورنج ليست حتمية بحيث أنَّه يوجد على الأكثر مسار حساب واحد اجابته «نعم». هذا القسم يحوي P ويحتويه القسم NP . (ar)
- En teoria de complexitat, la classe de complexitat UP és la classe de problemes de decisió que es poden resoldre en temps polinòmic en una per almenys un camí que accepte per cada entrada. Una reformulació de la definició de la classe NP s'expressa dient que un llenguatge és a NP si i només si donada una resposta, es pot verificar en un temps polinòmic per una màquina de Turing determinista. De manera similar, un llenguatge és a UP si donada una resposta es pot verificar en un temps polinòmic, i el verificador només accepta com a molt una resposta per cada instància del problema. Més formalment, un llenguatge L pertany a UP si existeix un algorisme de dues entrades i temps polinòmic A i una constant c tal que:
* si x és de L, llavors existeix un únic certificat y amb tal que
* si x no és de L, llavors no existeix un certificat y amb tal que
* l'algorisme A verifica L en un temps polinòmic (ca)
- En teoría de la complejidad computacional, la clase de complejidad UP (tiempo polinómico, no determinista, no ambiguo) es el conjunto de los problemas de decisión que pueden ser resueltos en tiempo polinómico por una máquina de Turing no determinista tal que la solución si existe es única. La clase UP está contenida en NP y contiene a P. No se sabe si estas inclusiones son estrictas. Un lenguaje L pertenece a UP si existe un algoritmo A de tiempo polinómico con dos entradas y una constante c tal que: L = {x in {0,1}* | ∃! valor, y con |y| = O(|x|c) tal que A(x,y) = 1}
* Datos: Q906584 (es)
- En théorie de la complexité, UP (en anglais : unambigous non-deterministic polynomial time) est la classe de complexité des problèmes de décision décidés par une machine de Turing non ambigüe (machine de Turing non-déterministe avec au plus une seule exécution acceptante pour une entrée donnée). Cette classe a été défini en 1976 par Valiant. (fr)
- In complexity theory, UP (unambiguous non-deterministic polynomial-time) is the complexity class of decision problems solvable in polynomial time on an unambiguous Turing machine with at most one accepting path for each input. UP contains P and is contained in NP. A common reformulation of NP states that a language is in NP if and only if a given answer can be verified by a deterministic machine in polynomial time. Similarly, a language is in UP if a given answer can be verified in polynomial time, and the verifier machine only accepts at most one answer for each problem instance. More formally, a language L belongs to UP if there exists a two-input polynomial-time algorithm A and a constant c such that if x in L , then there exists a unique certificate y with such that if x is not in L, there is no certificate y with such that algorithm A verifies L in polynomial time. UP (and its complement co-UP) contain both the integer factorization problem and parity game problem; because determined effort has yet to find a polynomial-time solution to any of these problems, it is suspected to be difficult to show P=UP, or even P=(UP ∩ co-UP). The Valiant–Vazirani theorem states that NP is contained in RPPromise-UP, which means that there is a randomized reduction from any problem in NP to a problem in Promise-UP. UP is not known to have any complete problems. (en)
- 계산 복잡도 이론에서 UP 곧, 모호하지 않은 비결정론적 다항 시간(Unambiguous non-deterministic Polynomial-time)이란 비결정론적 튜링 기계가 입력마다 받아들이는 경로를 최대 한 개만으로 해서 다항 시간에 풀 수 있는 판정 문제들의 복잡도 종류이다. UP는 P를 포함하고, NP에 속한다. P ≠ UP이거나 UP ≠ NP일 (아니면, 둘 다일) 것으로 추측하고 있다. 그렇지 않으면 P = NP이기 때문이다. (학계에서는 P ≠ NP일 것으로 보고 있다.) 두 가지 추측이 모두 참일 가능성이 높다. 흔히 NP를 이렇게 다시 형식화한다: 어떤 언어가 NP라는 것과 답이 주어질 때 결정론적 기계로 다항시간에 검증할 수 있다는 것은 동치이다. 비슷하게, 주어진 답이 다항 시간에 검증될 수 있고, 검증 기계가 문제 인스턴스마다 답변을 최대 한 개만 받아들이면, 그 언어는 UP이다. 더 형식적으로 쓰면, 언어 은 입력을 두 개 받는 다항 시간 알고리즘 A와 다음 조건을 만족하는 상수 c가 존재할 때 UP가 된다. 알고리즘 는 을 다항 시간에 검증한다. (ko)
- 計算複雑性理論において、複雑性クラス 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)
- Na teoria da complexidade, UP ("Tempo Polinomial Não-determinístico Não-ambíguo") é a classe de complexidade dos problemas de decisão resolvidos em tempo polinomial em uma máquina de Turing não ambígua com, no máximo, uma caminho de aceitação para cada entrada. UP contém P e está contida em NP. Uma reformulação costumeira de NP afirma que uma linguagem está em NP se e somente se uma determinada resposta pode ser verificada por uma máquina determinística em tempo polinomial. Da mesma forma, uma linguagem está em UP, se uma dada resposta pode ser verificada em tempo polinomial, e a máquina verificadora só aceita no máximo uma resposta para cada instância do problema. Mais formalmente, uma linguagem L pertence a UP se existe um algoritmo de tempo polinomial A de duas entradas e uma constante c tal que se x está em L , então existe um único certificado y com de tal forma que se x não está em L, não há nenhum certificado de y com de tal forma que o algoritmo A verifica L em tempo polinomial. UP (e seu complemento co-UP) contêm os problemas de fatoração de inteiros e do jogo de paridade; em razão do fato de que determinado esforço ainda tem que ser feito para encontrar uma solução em tempo-polinômial para qualquer um desses problemas, suspeita-se ser difícil mostrar que P=UP, ou mesmo P=(UP ∩ co-UP). O Teorema de Valiant-Vazirani afirma que NP está contida em RPPromise-UP, o que significa que há uma redução aleatorizada de qualquer problema em NP para um problema em Promise-UP. Não se sabe se UP tem algum problema completo. (pt)
- 在計算複雜度理論內，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）。 (zh)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 2164 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- في علم التعقيد الحسابي القسم UP هو قسم كل المسائل التي يمكن تقريرها بوقت كثير الحدود على آلة تيورنج ليست حتمية بحيث أنَّه يوجد على الأكثر مسار حساب واحد اجابته «نعم». هذا القسم يحوي P ويحتويه القسم NP . (ar)
- En teoría de la complejidad computacional, la clase de complejidad UP (tiempo polinómico, no determinista, no ambiguo) es el conjunto de los problemas de decisión que pueden ser resueltos en tiempo polinómico por una máquina de Turing no determinista tal que la solución si existe es única. La clase UP está contenida en NP y contiene a P. No se sabe si estas inclusiones son estrictas. Un lenguaje L pertenece a UP si existe un algoritmo A de tiempo polinómico con dos entradas y una constante c tal que: L = {x in {0,1}* | ∃! valor, y con |y| = O(|x|c) tal que A(x,y) = 1}
* Datos: Q906584 (es)
- En théorie de la complexité, UP (en anglais : unambigous non-deterministic polynomial time) est la classe de complexité des problèmes de décision décidés par une machine de Turing non ambigüe (machine de Turing non-déterministe avec au plus une seule exécution acceptante pour une entrée donnée). Cette classe a été défini en 1976 par Valiant. (fr)
- 계산 복잡도 이론에서 UP 곧, 모호하지 않은 비결정론적 다항 시간(Unambiguous non-deterministic Polynomial-time)이란 비결정론적 튜링 기계가 입력마다 받아들이는 경로를 최대 한 개만으로 해서 다항 시간에 풀 수 있는 판정 문제들의 복잡도 종류이다. UP는 P를 포함하고, NP에 속한다. P ≠ UP이거나 UP ≠ NP일 (아니면, 둘 다일) 것으로 추측하고 있다. 그렇지 않으면 P = NP이기 때문이다. (학계에서는 P ≠ NP일 것으로 보고 있다.) 두 가지 추측이 모두 참일 가능성이 높다. 흔히 NP를 이렇게 다시 형식화한다: 어떤 언어가 NP라는 것과 답이 주어질 때 결정론적 기계로 다항시간에 검증할 수 있다는 것은 동치이다. 비슷하게, 주어진 답이 다항 시간에 검증될 수 있고, 검증 기계가 문제 인스턴스마다 답변을 최대 한 개만 받아들이면, 그 언어는 UP이다. 더 형식적으로 쓰면, 언어 은 입력을 두 개 받는 다항 시간 알고리즘 A와 다음 조건을 만족하는 상수 c가 존재할 때 UP가 된다. 알고리즘 는 을 다항 시간에 검증한다. (ko)
- 計算複雑性理論において、複雑性クラス 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"，非模糊非決定型多項式時間）是一個決定型問題的複雜度類，能以非決定型圖靈機在多項式時間內解決，且對任何輸入只有至多一條接受的路徑。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）。 (zh)
- En teoria de complexitat, la classe de complexitat UP és la classe de problemes de decisió que es poden resoldre en temps polinòmic en una per almenys un camí que accepte per cada entrada. Una reformulació de la definició de la classe NP s'expressa dient que un llenguatge és a NP si i només si donada una resposta, es pot verificar en un temps polinòmic per una màquina de Turing determinista. De manera similar, un llenguatge és a UP si donada una resposta es pot verificar en un temps polinòmic, i el verificador només accepta com a molt una resposta per cada instància del problema. Més formalment, un llenguatge L pertany a UP si existeix un algorisme de dues entrades i temps polinòmic A i una constant c tal que: (ca)
- In complexity theory, UP (unambiguous non-deterministic polynomial-time) is the complexity class of decision problems solvable in polynomial time on an unambiguous Turing machine with at most one accepting path for each input. UP contains P and is contained in NP. if x in L , then there exists a unique certificate y with such that if x is not in L, there is no certificate y with such that algorithm A verifies L in polynomial time. UP is not known to have any complete problems. (en)
- Na teoria da complexidade, UP ("Tempo Polinomial Não-determinístico Não-ambíguo") é a classe de complexidade dos problemas de decisão resolvidos em tempo polinomial em uma máquina de Turing não ambígua com, no máximo, uma caminho de aceitação para cada entrada. UP contém P e está contida em NP. se x está em L , então existe um único certificado y com de tal forma que se x não está em L, não há nenhum certificado de y com de tal forma que o algoritmo A verifica L em tempo polinomial. Não se sabe se UP tem algum problema completo. (pt)
|
| rdfs:label
|
- يو بي (تعقيد حسابي) (ar)
- UP (Complexitat) (ca)
- UP (clase de complejidad) (es)
- UP (complexité) (fr)
- UP (計算複雑性理論) (ja)
- UP (복잡도) (ko)
- UP (complexidade) (pt)
- UP (complexity) (en)
- UP (複雜度) (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
