| dbo:abstract
|
- En teoria de la complexitat, la classe de complexitat RP (Randomized polynomial time) és el conjunt dels problemes de decisió tals que una màquina de Turing probabilística existeix amb aquestes propietats:
* sempre s'executa amb un temps polinòmic segons la mida de l'entrada
* si la solució és NO, sempre respon NO
* si la solució és SI, retorna SI amb una probabilitat d'almenys 1/2 (en cas contrari, retorna NO) En d'altre paraules, l'algorisme pot prendre decisions aleatòries, l'únic cas en què l'algorisme retorna SI és si la resposta correcta del problema és SI. Per tant, si la màquina acaba i respon SI, la resposta correcta és SI. Tot i això, l'algorisme pot acabar i respondre NO i estar equivocat. La fracció d'1/2 de la definició és arbitrària i es pot canviar per qualsevol altre probabilitat menor d'1 sense que canviïn els problemes que entren dins d'aquesta classe. Si la resposta correcta és SI i l'algorisme s'executa m cops, el resultat de cada execució és independent un de l'altra i almenys respondrà amb SI 1-2-m cops. Així es te que si s'executa un algorisme d'aquest tipus 100 cops, la probabilitat que doni la resposta errònia cada vegada és més baixa que la probabilitat que els raigs còsmics puguin corrompre la memòria de l'ordinador executant l'algorisme. En aquest sentit, si hi ha un bona font d'atzar, molts algorismes d'aquesta classe son practicables. (ca)
- في علم التعقيد الحسابي RP أو Randomized Polynomial time هو قسم المسائل التي تقريرها بوقت حدودي بواسطة آلة تيورنج احتمالية مع الخاصية التالية:
* إذا كان المُدخل جوابه نعم حينها احتمال أن الجواب هو نعم أكبر من
* إذا كان المُدخل جوابه لا حينها احتمال ان الجواب هو لا هو 1 . أي انه إذا كان الجواب نعم فهو حتما نعم اما إذا كان الجواب لا فانه باحتمال 1/2 على الأقل ان يكون الجواب لا . يمكن استبدال الثابت 1/2 بأي عدد لا يساوي 0 اقل من 1 . (ar)
- V teorii složitosti je RP jednou z významných . Obsahuje všechny problémy řešitelné pomocí randomizovaného Turingova stroje v polynomiálním množství času s tím, že na kladné odpovědi stroje je možno se spolehnout. RP je obvykle považována za třídu problémů, které jsou efektivně řešitelné (existují ale i další třídy považované za efektivně řešitelné, jako P a BPP), přesto není v této třídě problém najít i efektivně neřešitelné problémy (se složitostí například N1000000). (cs)
- RP (englisch randomized polynomial time, manchmal auch nur mit R bezeichnet) bezeichnet die Klasse der Entscheidungsprobleme, für die es einen randomisierten Algorithmus mit polynomieller Laufzeit gibt, der jede nicht zu akzeptierende Eingabe mit Wahrscheinlichkeit 1 ablehnt und für jede zu akzeptierende Eingabe eine Fehlerwahrscheinlichkeit von höchstens 1/2 hat. Die Verwendung einer beliebigen anderen konstanten Fehlerschranke kleiner als 1 ändert nichts an der Definition der Klasse RP, durch mehrmalige Anwendung eines gegebenen RP-Algorithmus lässt sich jede beliebige Fehlerschranke erreichen. Dieser Fehlertyp wird als einseitiger Fehler (one-sided error) bezeichnet, im Gegensatz zu dem zweiseitigen Fehler (two-sided error) bei der Komplexitätsklasse BPP. Sie wurde 1977 mit anderen probabilistichen Komplexitätsklassen von John T. Gill eingeführt. (de)
- En , RP (iam nomata kiel R) ("hazardigita polinoma tempo") estas de kiuj povas esti solvitaj per probableca maŝino de Turing en polinoma tempo kun ĉi tiuj probablecoj de la rezultoj: Alivorte, la algoritmo havas jenajn propraĵojn:
* Ĝi ĉiam ruliĝas en polinoma tempo en la eniga amplekso.
* Se la ĝusta respondo estas "ne", ĝi ĉiam redonas respondon "ne".
* Se la ĝusta respondo estas "jes", tiam ĝi redonas respondon "jes" kun probablo minimume 1/2 (alie, ĝi redonas respondon "ne"). Tiel la sola okazo en kiu la algoritmo povas redoni respondon "jes" estas se la ĝusta respondo estas "jes". Pro tio se la algoritmo redonas respondon "jes", do la ĝusta respondo estas definitive "jes". Tamen, se la algoritmo redonas respondon "ne", la ĝusta repondo ne estas ankoraŭ sciata. Se la ĝusta respondo estas "jes" kaj la algoritmo estas ruliĝas n fojojn kun la rezultoj de la ruliĝoj estas statistike sendependaj unu de la aliaj, tiam ĝi redonas respondon "jes" almenaŭ unufoje kun probablo almenaŭ 1 - (1/2)n. Kutime la algoritmo, krom la ĉefa enigo, prenas iun hazardan variablon, de valoro de kiu dependas la rezulto en la necerta okazo. Kutima uzo ĉi tiaj algoritmoj estas jena:
* Riligi la algoritmon multfoje, ĉiu foje kun la nova valoro de la hazarda variablo.
* Se almenaŭ unu redonita respondo estas "jes" do opinii ke la ĝusta respondo estas "jes" (certe).
* Se ĉiam redonita respondo estas "ne" do opinii ke la ĝusta respondo estas "ne" (preskaŭ certe). Tiel se la algoritmo ruliĝas 200 fojojn do la ŝanco de ricevo de la erara respondo estas pli malgranda ol la ŝanco ke kosma radiado fuŝas memoron de la komputilo. En ĉi tiu senco, se fonto de stokastoj estas havebla, plej parto de ĉi tiaj algoritmoj estas praktika. La frakcio 1/2 en la difino povas esti anstataŭigita per iu ajn la alia p, 0, la aro RP de la ŝanĝo ne ŝanĝiĝas. Nur bezonatas la alia kvanto de riliĝoj de la algoritmo por la sama probableco de eraro, kaj la kvanto ne dependas de la amplekso de la enigo kaj tiel la ordo de rula tempo ne ŝanĝiĝas.. (eo)
- En informatique théorique, plus précisément en théorie de la complexité, la classe RP (Randomized Polynomial time) est la classe de complexité des problèmes de décision pour lesquels il existe une machine de Turing probabiliste, en temps polynomial, qui refuse toutes les instances négatives et accepte les instances positives avec une probabilité supérieure à 1/2. (fr)
- In computational complexity theory, randomized polynomial time (RP) is the complexity class of problems for which a probabilistic Turing machine exists with these properties:
* It always runs in polynomial time in the input size
* If the correct answer is NO, it always returns NO
* If the correct answer is YES, then it returns YES with probability at least 1/2 (otherwise, it returns NO). In other words, the algorithm is allowed to flip a truly random coin while it is running. The only case in which the algorithm can return YES is if the actual answer is YES; therefore if the algorithm terminates and produces YES, then the correct answer is definitely YES; however, the algorithm can terminate with NO regardless of the actual answer. That is, if the algorithm returns NO, it might be wrong. Some authors call this class R, although this name is more commonly used for the class of recursive languages. If the correct answer is YES and the algorithm is run n times with the result of each run statistically independent of the others, then it will return YES at least once with probability at least 1 − 2−n. So if the algorithm is run 100 times, then the chance of it giving the wrong answer every time is lower than the chance that cosmic rays corrupted the memory of the computer running the algorithm. In this sense, if a source of random numbers is available, most algorithms in RP are highly practical. The fraction 1/2 in the definition is arbitrary. The set RP will contain exactly the same problems, even if the 1/2 is replaced by any constant nonzero probability less than 1; here constant means independent of the input to the algorithm. (en)
- 計算複雑性理論におけるRP(randomized polynomial time)とは、以下の3つの属性を持つ確率的チューリング機械で解ける問題の複雑性クラスである。
* 入力長に対して常に多項式時間かかる。
* 正解が NO である場合、常に NO を返す。
* 正解が YES である場合、確率 ½ 以上で YES を返す（そうでない場合、NO を返す）。 換言すれば、そのアルゴリズムは、実行中に完全に無作為なコインを投げているようなものである。このアルゴリズムが YES を返すのは、実際の答えが YES であるときだけである。したがって、アルゴリズムが停止して YES を生成した場合、正解は必ず YES である。しかし、NO を返して停止する場合、実際の答えが何であるかはわからない。つまり、NO を返したとき、それは間違っている可能性がある。 この複雑性クラスを R と呼ぶこともあるが、一般に R と言えば帰納言語のクラスの名称として使われている。 正解が YES であるとき、このアルゴリズムを n 回試行し、各試行には確率論的独立性があるとき、YES が少なくとも 1回返される確率は 1 - ½n 以上である。従って、100回試行すれば回答が間違っている確率は、宇宙線がコンピュータのメモリの内容を破壊して計算結果を間違う可能性よりも低くなる。従って、乱数発生源があれば、RP に属するアルゴリズムの多くは極めて実用的となる。 ½ という割合は実際には任意の割合でよい。½ が 0 より大きく 1 より小さい任意の割合でありさえすれば、RP に属する問題の性質は変わらない。この定数はアルゴリズムの入力の内容や長さとは無関係である。 (ja)
- Nella teoria della complessità computazionale, RP (Randomized Polynomial time, "tempo polinomiale randomizzato") è la classe di complessità dei problemi decisionali eseguiti su una macchina di Turing probabilistica. Si può inoltre definire una classe molto vicina: co-RP. (it)
- 복잡도 이론에서 RP (확률적 다항시간, randomized polynomial time)은 다음과 같은 성질을 만족하는 확률적 튜링 기계가 존재하는 문제들의 복잡도 종류이다.
* 확률적 튜링 기계의 실행시간은 입력의 크기를 기준으로 다항시간이어야 한다.
* 실제 결과가 '아니오'일 때, 확률적 튜링 기계의 실행결과는 항상 '아니오'이다.
* 실제 결과가 '예'일 때, 확률적 튜링 기계의 실행결과는 최소 1/2의 확률로 '예'라는 결과를 내놓는다. 알고리즘으로 표현하자면, 확률적으로 진행하면서 실제 결과가 '예'일 때만 '예'라는 답을 내놓는 알고리즘이다. 그러므로 알고리즘 실행결과 '예'라는 결과가 나왔으면, 실제 결과는 항상 '예'이다. 그러나 알고리즘 실행결과 '아니오'가 나왔으면 실제로는 '예'일 수도 있고 '아니오'일 수도 있다. 일부 사람들은 이 복잡도 종류를 RP 대신 R이라고 하는 경우도 있으나, R은 보통 재귀 언어 종류를 가리킬 때 사용한다. (ko)
- Tempo Polinomial Aleatorizado (em inglês, Randomized polynomial time: RP) é uma classe de complexidade da complexidade computacional, problemas para nos quais a Máquina de Turing probabilística possui as seguintes propriedades:
* Sempre roda em tempo polinomial no tamanho da entrada
* Se a resposta correta é NÃO, ele sempre retorna NÃO
* Se a resposta correta for SIM, então ele tem uma probabilidade de 1/2 de retornar SIM (caso contrario, retorna NÃO). Em outras palavras, o algoritmo permite jogar uma moeda realmente aleatória enquanto está rodando. O único caso no qual o algoritmo pode retornar SIM é quando a resposta é realmente SIM; portanto se o algoritmo termina e produz SIM, então a resposta correta é definitivamente SIM; entretanto, o algoritmo pode terminar com NÃO independentemente da verdadeira resposta. Ou seja, se o algoritmo retornar NÃO, ele pode estar errado. Alguns autores chamam essa classe de R, entretanto esse nome é mais comumente usado para a classe das linguagens recursivas. Se a resposta correta é SIM e o algoritmo for executado n vezes com o resultado de cada execução estatisticamente independente dos outros, então ele vai retornar SIM pelo menos uma vez com uma probabilidade de pelo menos 1 − 2−n. Logo, se o algoritmo executar 100 vezes, então a chance dele retornar a resposta errada todas as vezes é menor do que a chance de que raios cósmicos corrompam a memória do computador que esteja rodando o algoritmo. Dessa forma, se a fonte dos números aleatórios estiver disponível, a maior parte dos algoritmos em RP são altamente práticos. A fração 1/2 na definição é arbitraria. O conjunto RP conterá exatamente os mesmos problemas, mesmo que 1/2 seja substituída por qualquer probabilidade constante diferente de zero e menor que 1; aqui constante significa independência da entrada do algoritmo. (pt)
- 在複雜度理論內，RP（"隨機多項式時間"）是一個有關機率圖靈機的複雜度類，並且存在以下特性：
* 此演算法總是跑輸入大小的多項式長度這麼多的時間
* 如果輸入的答案為非，此演算法會回傳NO
* 如果輸入的答案為是，則回傳YES的機率至少1/2（其餘的機率則是回傳NO）。 換句話說，這個演算法允許在操作的時候進行全然機率的猜測。這個演算法會回傳YES的狀況必然是輸入為真的狀況；因此如果這個演算法說了YES，那我們就知道了這個輸入必定為是：不過，這個演算法可以在不管正確解答為何的時候回傳NO。也就是，如果這個演算法回傳答案是錯的，可能是這個演算法犯錯了（也就是其實這個輸入應該是對的）。 有一些作者叫這一個複雜度類R，不過這個名字更常被使用於定義包含了所有遞歸語言的複雜度類。 如果輸入的答案為"是"且這個演算法運作了n次，每次跑出來的答案於其他答案，那回傳起碼一次YES的機率則至少有1 − 2−n這麼多。所以如果這個演算法跑了夠多的次數，那數學上來說他回傳錯誤解答的機率就會變得非常非常小，甚至小過運算的電腦被宇宙射線影響因此錯誤的機率。在這個概念上，如果我們有一個夠好的亂數來源，大多數的RP演算法都是非常具有實做價值的。 這裡選用的1/2這個常數，是不需要太嚴格的一個選擇：無論我們將定義裡面的1/2換成任何小於1的非零常數，RP這個集合仍舊包含了所有原來的問題。（這裡的常數代表說此數字跟輸入沒有任何關係） (zh)
- Будем считать, что язык L принадлежит классу RP («randomized polynomial class» — случайный полиномиальный), если он допускается вероятностной машиной Тьюринга M, для которой выполнены следующие условия:
* Если w не принадлежит L, то вероятность того, что M допускает w, равна 0.
* Если w принадлежит L, то вероятность того, что M допускает w, не меньше ½.
* Существует полином p(n), для которого, если w имеет длину n, то вычисления M останавливаются после не более p(n) шагов (независимо от содержимого случайной ленты). Примечание. Определение класса RP использует два понятия, которые не связаны между собой:
* В пунктах 1 и 2 определяется рандомизированная машина Тьюринга, которая называется машиной типа Монте-Карло.
* В пункте 3 говорится о времени работы, которое не зависит от того, является ли данная машина Тьюринга машиной типа Монте-Карло. Примечание. Выбор в качестве порога ½ в данном случае не обязателен и данную константу можно заменить на другую (0 < < 1). При этом RP будет содержать те же задачи, но языки, определяемые конкретными рандомизированными машинами Тьюринга, изменятся. (ru)
|
| rdfs:comment
|
- في علم التعقيد الحسابي RP أو Randomized Polynomial time هو قسم المسائل التي تقريرها بوقت حدودي بواسطة آلة تيورنج احتمالية مع الخاصية التالية:
* إذا كان المُدخل جوابه نعم حينها احتمال أن الجواب هو نعم أكبر من
* إذا كان المُدخل جوابه لا حينها احتمال ان الجواب هو لا هو 1 . أي انه إذا كان الجواب نعم فهو حتما نعم اما إذا كان الجواب لا فانه باحتمال 1/2 على الأقل ان يكون الجواب لا . يمكن استبدال الثابت 1/2 بأي عدد لا يساوي 0 اقل من 1 . (ar)
- V teorii složitosti je RP jednou z významných . Obsahuje všechny problémy řešitelné pomocí randomizovaného Turingova stroje v polynomiálním množství času s tím, že na kladné odpovědi stroje je možno se spolehnout. RP je obvykle považována za třídu problémů, které jsou efektivně řešitelné (existují ale i další třídy považované za efektivně řešitelné, jako P a BPP), přesto není v této třídě problém najít i efektivně neřešitelné problémy (se složitostí například N1000000). (cs)
- En informatique théorique, plus précisément en théorie de la complexité, la classe RP (Randomized Polynomial time) est la classe de complexité des problèmes de décision pour lesquels il existe une machine de Turing probabiliste, en temps polynomial, qui refuse toutes les instances négatives et accepte les instances positives avec une probabilité supérieure à 1/2. (fr)
- Nella teoria della complessità computazionale, RP (Randomized Polynomial time, "tempo polinomiale randomizzato") è la classe di complessità dei problemi decisionali eseguiti su una macchina di Turing probabilistica. Si può inoltre definire una classe molto vicina: co-RP. (it)
- 복잡도 이론에서 RP (확률적 다항시간, randomized polynomial time)은 다음과 같은 성질을 만족하는 확률적 튜링 기계가 존재하는 문제들의 복잡도 종류이다.
* 확률적 튜링 기계의 실행시간은 입력의 크기를 기준으로 다항시간이어야 한다.
* 실제 결과가 '아니오'일 때, 확률적 튜링 기계의 실행결과는 항상 '아니오'이다.
* 실제 결과가 '예'일 때, 확률적 튜링 기계의 실행결과는 최소 1/2의 확률로 '예'라는 결과를 내놓는다. 알고리즘으로 표현하자면, 확률적으로 진행하면서 실제 결과가 '예'일 때만 '예'라는 답을 내놓는 알고리즘이다. 그러므로 알고리즘 실행결과 '예'라는 결과가 나왔으면, 실제 결과는 항상 '예'이다. 그러나 알고리즘 실행결과 '아니오'가 나왔으면 실제로는 '예'일 수도 있고 '아니오'일 수도 있다. 일부 사람들은 이 복잡도 종류를 RP 대신 R이라고 하는 경우도 있으나, R은 보통 재귀 언어 종류를 가리킬 때 사용한다. (ko)
- En teoria de la complexitat, la classe de complexitat RP (Randomized polynomial time) és el conjunt dels problemes de decisió tals que una màquina de Turing probabilística existeix amb aquestes propietats:
* sempre s'executa amb un temps polinòmic segons la mida de l'entrada
* si la solució és NO, sempre respon NO
* si la solució és SI, retorna SI amb una probabilitat d'almenys 1/2 (en cas contrari, retorna NO) La fracció d'1/2 de la definició és arbitrària i es pot canviar per qualsevol altre probabilitat menor d'1 sense que canviïn els problemes que entren dins d'aquesta classe. (ca)
- En , RP (iam nomata kiel R) ("hazardigita polinoma tempo") estas de kiuj povas esti solvitaj per probableca maŝino de Turing en polinoma tempo kun ĉi tiuj probablecoj de la rezultoj: Alivorte, la algoritmo havas jenajn propraĵojn:
* Ĝi ĉiam ruliĝas en polinoma tempo en la eniga amplekso.
* Se la ĝusta respondo estas "ne", ĝi ĉiam redonas respondon "ne".
* Se la ĝusta respondo estas "jes", tiam ĝi redonas respondon "jes" kun probablo minimume 1/2 (alie, ĝi redonas respondon "ne"). (eo)
- RP (englisch randomized polynomial time, manchmal auch nur mit R bezeichnet) bezeichnet die Klasse der Entscheidungsprobleme, für die es einen randomisierten Algorithmus mit polynomieller Laufzeit gibt, der jede nicht zu akzeptierende Eingabe mit Wahrscheinlichkeit 1 ablehnt und für jede zu akzeptierende Eingabe eine Fehlerwahrscheinlichkeit von höchstens 1/2 hat. Die Verwendung einer beliebigen anderen konstanten Fehlerschranke kleiner als 1 ändert nichts an der Definition der Klasse RP, durch mehrmalige Anwendung eines gegebenen RP-Algorithmus lässt sich jede beliebige Fehlerschranke erreichen. (de)
- In computational complexity theory, randomized polynomial time (RP) is the complexity class of problems for which a probabilistic Turing machine exists with these properties:
* It always runs in polynomial time in the input size
* If the correct answer is NO, it always returns NO
* If the correct answer is YES, then it returns YES with probability at least 1/2 (otherwise, it returns NO). Some authors call this class R, although this name is more commonly used for the class of recursive languages. (en)
- 計算複雑性理論におけるRP(randomized polynomial time)とは、以下の3つの属性を持つ確率的チューリング機械で解ける問題の複雑性クラスである。
* 入力長に対して常に多項式時間かかる。
* 正解が NO である場合、常に NO を返す。
* 正解が YES である場合、確率 ½ 以上で YES を返す（そうでない場合、NO を返す）。 換言すれば、そのアルゴリズムは、実行中に完全に無作為なコインを投げているようなものである。このアルゴリズムが YES を返すのは、実際の答えが YES であるときだけである。したがって、アルゴリズムが停止して YES を生成した場合、正解は必ず YES である。しかし、NO を返して停止する場合、実際の答えが何であるかはわからない。つまり、NO を返したとき、それは間違っている可能性がある。 この複雑性クラスを R と呼ぶこともあるが、一般に R と言えば帰納言語のクラスの名称として使われている。 ½ という割合は実際には任意の割合でよい。½ が 0 より大きく 1 より小さい任意の割合でありさえすれば、RP に属する問題の性質は変わらない。この定数はアルゴリズムの入力の内容や長さとは無関係である。 (ja)
- Tempo Polinomial Aleatorizado (em inglês, Randomized polynomial time: RP) é uma classe de complexidade da complexidade computacional, problemas para nos quais a Máquina de Turing probabilística possui as seguintes propriedades:
* Sempre roda em tempo polinomial no tamanho da entrada
* Se a resposta correta é NÃO, ele sempre retorna NÃO
* Se a resposta correta for SIM, então ele tem uma probabilidade de 1/2 de retornar SIM (caso contrario, retorna NÃO). Alguns autores chamam essa classe de R, entretanto esse nome é mais comumente usado para a classe das linguagens recursivas. (pt)
- Будем считать, что язык L принадлежит классу RP («randomized polynomial class» — случайный полиномиальный), если он допускается вероятностной машиной Тьюринга M, для которой выполнены следующие условия:
* Если w не принадлежит L, то вероятность того, что M допускает w, равна 0.
* Если w принадлежит L, то вероятность того, что M допускает w, не меньше ½.
* Существует полином p(n), для которого, если w имеет длину n, то вычисления M останавливаются после не более p(n) шагов (независимо от содержимого случайной ленты). (ru)
- 在複雜度理論內，RP（"隨機多項式時間"）是一個有關機率圖靈機的複雜度類，並且存在以下特性：
* 此演算法總是跑輸入大小的多項式長度這麼多的時間
* 如果輸入的答案為非，此演算法會回傳NO
* 如果輸入的答案為是，則回傳YES的機率至少1/2（其餘的機率則是回傳NO）。 換句話說，這個演算法允許在操作的時候進行全然機率的猜測。這個演算法會回傳YES的狀況必然是輸入為真的狀況；因此如果這個演算法說了YES，那我們就知道了這個輸入必定為是：不過，這個演算法可以在不管正確解答為何的時候回傳NO。也就是，如果這個演算法回傳答案是錯的，可能是這個演算法犯錯了（也就是其實這個輸入應該是對的）。 有一些作者叫這一個複雜度類R，不過這個名字更常被使用於定義包含了所有遞歸語言的複雜度類。 如果輸入的答案為"是"且這個演算法運作了n次，每次跑出來的答案於其他答案，那回傳起碼一次YES的機率則至少有1 − 2−n這麼多。所以如果這個演算法跑了夠多的次數，那數學上來說他回傳錯誤解答的機率就會變得非常非常小，甚至小過運算的電腦被宇宙射線影響因此錯誤的機率。在這個概念上，如果我們有一個夠好的亂數來源，大多數的RP演算法都是非常具有實做價值的。 (zh)
|
