ZPP (complexity)
http://dbpedia.org/resource/ZPP_(complexity) an entity of type: WikicatComplexityClasses
في نظرية التعقيد الحسابي القسم ZPP هو قسم كل المسائل التي يمكن تقريرها بواسطة آلة تيورنج احتمالية بوقت حدودي مع إمكانية الفشل في الاتيان بجواب، أيضا تعريف هذا القسم بأنه قسم كل المسائل التي يمكن تقريرها بواسطة آلة تيورنج احتمالية التي لا تخطئ أبدًا بحيث أن وقتها المتوقع (expected running time) هو حدودي أي أي لو أن الخوارزمية ترمي قطع نقدية عشوائية خلال وقت عملها فإنَّ جوابها صحيح دائما ولكن معدل وقت عملها لكل مُدخل طوله هو (p(n ، حيث أنَّ (p(n هو كثير حدود، القول الاخير يعني انه بشكل عام وقت عمل الخوارزمية هو كثير حدود ولكن يمكن أن يكون هناك مُدخلات بحيث أن وقت عمل الخوارزمية أكثر من حدودي. التعريفان متكافئان.
rdf:langString
La classe ZPP, est un objet de la théorie de la complexité, en informatique théorique. C'est une classe de problèmes de décision sur machine de Turing probabiliste. L'acronyme ZPP vient de Zero-Error Probabilistic Polynomial time.
rdf:langString
在計算複雜度理論內, ZPP（zero-error probabilistic polynomial time，零錯誤概率多項式時間）是一個與機率圖靈機有關的的複雜度類，並且存在以下特點：
* 這機器永遠會給出正確的"是"或者"否"的答案。
* 這個機器平均運作的時間是多項式時間以內。 換句話說，有一個演算法會在運作時使用一個完美隨機的硬幣，並且永遠回傳正確的答案（這種演算法被稱作拉斯維加斯演算法（Las Vegas algorithm））。對一個輸入大小為n的問題，存在一個多項式p(n)，令平均的運作時間小於p(n)（有可能偶爾會超過）。 另外，ZPP可以定義為一個問題的集合，裡面每個問題都存在一個可以解決此問題的機率圖靈機，且此機器性質如下：
* 運轉時間永遠是多項式時間
* 會回傳YES，NO或者DO NOT KNOW的答案
* 答案如果不是DO NOT KNOW，就會是正確的答案
* 如果問題的正確答案是YES，這機器回傳YES的機率至少是1/2（其他時候回傳DO NOT KNOW）
* 如果問題的正確答案是NO，這機器回傳NO的機率至少是1/2（其他時候回傳DO NOT KNOW） 以上這兩個定義是相等的。ZPP的定義是基於概率圖靈機。其他基於概率圖靈機的複雜度類包含了BPP和RP。至於BQP (複雜度)這個複雜度類則換成使用了量子電腦這種也是具有隨機性的電腦。
rdf:langString
En teoria de la complexitat, la classe de complexitat ZPP (zero error probabilistic polynomial time) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing probabilística tal que
* sempre retorna la resposta correcta, ja sigui SI o NO
* el temps d'execució és polinòmic per cada mida de l'entrada La definició de ZPP està basada en la màquina de Turing probabilística, com les definicions de les classes BPP i RP. La classe BQP també està basada en una màquina amb atzar com és el computador quàntic.
rdf:langString
Die Komplexitätsklasse ZPP (englisch zero-error probabilistic polynomial time) beinhaltet alle Probleme, für die es eine nichtdeterministische Turingmaschine gibt, die an jeder Stelle mit gleicher Wahrscheinlichkeit unter den möglichen Alternativen auswählt und folgende Eigenschaften besitzt:
* Sie gibt immer die richtige Antwort zurück (daher "zero-error")
* Die Laufzeit ist nicht begrenzt, jedoch existiert ein Polynom, durch das die mittlere Laufzeit begrenzt ist Der randomisierte Algorithmus ist also korrekt, kann aber mitunter eine sehr viel längere Laufzeit als im typischen Fall haben.
rdf:langString
In complexity theory, ZPP (zero-error probabilistic polynomial time) is the complexity class of problems for which a probabilistic Turing machine exists with these properties:
* It always returns the correct YES or NO answer.
* The running time is polynomial in expectation for every input. Alternatively, ZPP can be defined as the class of problems for which a probabilistic Turing machine exists with these properties: The two definitions are equivalent.
rdf:langString
計算複雑性理論における ZPP とは、以下の属性をもつ確率的チューリング機械で解ける問題の複雑性クラスである。
* YES または NO の常に正しい解を返す。
* 実行時間に制限はないが、任意の入力長について平均で多項式時間かかる。 なお ZPP とは "Zero-error Probabilistic Polynomial time" の略である。 換言すれば、ZPP に属する問題を解くアルゴリズムは完全に無作為なコインを投げるとも言える。常に正しい答えを返すので、ラスベガス法に分類される。入力長 n に関する多項式 p(n) があるとき、答えを得るまでにかかる時間の平均は p(n) 未満だが、最悪の場合はもっと長くなる。 あるいは、ZPP を以下の属性を持つ確率的チューリング機械で解ける問題のクラスと定義することもできる。
* 常に多項式時間である。
* 解として YES、NO、DO NOT KNOW の三種類を返す。
* 解は DO NOT KNOW でない場合は常に正しい。
* 正解が YES である場合、YES を返す確率は最低でも 1/2 である。
* 正解が NO である場合、NO を返す確率は最低でも 1/2 である。 これら2つの定義は等価である。
rdf:langString
계산 복잡도 이론에서 복잡도 종류 ZPP(오차 없는 확률적 다항시간, Zero-error Probabilistic Polynomial time)는 다음과 같은 성질을 지니는 확률적 튜링 기계가 존재하는 문제로 이루어진 집합이다.
* 항상 올바른 '예' 또는 '아니오' 답을 내놓는다.
* 최대 실행시간은 정해져 있지 않으나, 어떠한 입력에 대해서도 평균 다항 시간에 실행한다. 이는 문제 크기가 n이면 평균 실행 시간이 p(n)보다 작게 되는 다항식 p(n)이 존재한다는 뜻도 된다. (평균 실행 시간이 그렇다는 것이고, 각 실행은 훨씬 오래 걸릴 수 있다.) ZPP에 속한 알고리즘은 항상 올바른 답을 내놓는다. (이러한 알고리즘을 이라고 한다.) 다른 식으로 정의할 수도 있다. ZPP란 다음과 같은 성질을 지니는 확률적 튜링 기계가 존재하는 문제의 복잡도 종류이다.
* 항상 다항 시간에 실행을 마친다.
* '예', '아니오', '알 수 없음' 중 하나를 답으로 내놓는다.
* 답은 '알 수 없음'이거나 정답이어야 한다.
* 정답이 '예'라면 1/2 확률로 '예'를 답으로 내놓는다.
* 정답이 '아니오'라면 1/2 확률로 '아니오'를 답으로 내놓는다.
rdf:langString
Nella teoria della complessità computazionale, ZPP (Zero-error Probabilistic Polynomial time, "tempo polinomiale probabilistico con errore zero") è la classe di complessità dei problemi per i quali esiste una macchina di Turing probabilistica con queste proprietà
* Restituisce sempre la risposta corretta SÌ o NO.
* Il tempo di esecuzione è polinomiale in termini di aspettativa per ogni input. Alternativamente, ZPP può essere definita come la classe dei problemi per i quali esiste una macchina di Turing probabilistica con queste proprietà: Le due definizioni sono equivalenti.
rdf:langString
Na Teoria da complexidade computacional, ZPP (inglês: Zero-error Probabilistic Polinomial time, Probalístico de tempo polinominal sem erros) é a classe complexa de problemas em que uma Máquina de Turing existe com estas propriedades:
* Sempre retorna a resposta correta SIM ou NÃO.
* O tempo de execução é irrestrito, mas é polinominal para cada entrada. Podemos dizer também que, ZPP pode ser definido como a classe de problemas em que uma Máquina de Turing existe com estas propriedades:
rdf:langString
В теории вычислительной сложности ZPP (англ. zero-error probabilistic polynomial time — безошибочный вероятностный полиномиальный) — это класс задач с ответом «Да» либо «Нет», для которых существует вероятностная машина Тьюринга, удовлетворяющая следующим свойствам:
* Она всегда правильно отвечает «Да» либо «Нет».
* Математическое ожидание времени работы данной машины Тьюринга полиномиально (само время работы может быть неограниченно велико). Существует альтернативный набор свойств:
rdf:langString
rdf:langString
ZPP (تعقيد حسابي)
rdf:langString
ZPP (Complexitat)
rdf:langString
ZPP (Komplexitätsklasse)
rdf:langString
ZPP (complexité)
rdf:langString
ZPP (complessità)
rdf:langString
ZPP
rdf:langString
ZPP
rdf:langString
ZPP
rdf:langString
ZPP (complexity)
rdf:langString
Класс ZPP
rdf:langString
ZPP (複雜度)
xsd:integer
54772
xsd:integer
1015241762
rdf:langString
En teoria de la complexitat, la classe de complexitat ZPP (zero error probabilistic polynomial time) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing probabilística tal que
* sempre retorna la resposta correcta, ja sigui SI o NO
* el temps d'execució és polinòmic per cada mida de l'entrada Dit d'una altra manera, l'algorisme pot prendre decisions aleatòries. sempre retorna la resposta correcta i per un problema de mida n, de mitjana, el temps d'execució és menor d'un polinomi p(n) tot i que algunes execucions poden ser molt més llargues. A aquest tipus d'algorismes també se'ls coneix algorismes Las Vegas. La definició de ZPP està basada en la màquina de Turing probabilística, com les definicions de les classes BPP i RP. La classe BQP també està basada en una màquina amb atzar com és el computador quàntic.
rdf:langString
في نظرية التعقيد الحسابي القسم ZPP هو قسم كل المسائل التي يمكن تقريرها بواسطة آلة تيورنج احتمالية بوقت حدودي مع إمكانية الفشل في الاتيان بجواب، أيضا تعريف هذا القسم بأنه قسم كل المسائل التي يمكن تقريرها بواسطة آلة تيورنج احتمالية التي لا تخطئ أبدًا بحيث أن وقتها المتوقع (expected running time) هو حدودي أي أي لو أن الخوارزمية ترمي قطع نقدية عشوائية خلال وقت عملها فإنَّ جوابها صحيح دائما ولكن معدل وقت عملها لكل مُدخل طوله هو (p(n ، حيث أنَّ (p(n هو كثير حدود، القول الاخير يعني انه بشكل عام وقت عمل الخوارزمية هو كثير حدود ولكن يمكن أن يكون هناك مُدخلات بحيث أن وقت عمل الخوارزمية أكثر من حدودي. التعريفان متكافئان.
rdf:langString
Die Komplexitätsklasse ZPP (englisch zero-error probabilistic polynomial time) beinhaltet alle Probleme, für die es eine nichtdeterministische Turingmaschine gibt, die an jeder Stelle mit gleicher Wahrscheinlichkeit unter den möglichen Alternativen auswählt und folgende Eigenschaften besitzt:
* Sie gibt immer die richtige Antwort zurück (daher "zero-error")
* Die Laufzeit ist nicht begrenzt, jedoch existiert ein Polynom, durch das die mittlere Laufzeit begrenzt ist Der randomisierte Algorithmus ist also korrekt, kann aber mitunter eine sehr viel längere Laufzeit als im typischen Fall haben. Für alle Probleme aus ZPP existiert auch eine probabilistische Turingmaschine, die immer eine polynomial begrenzte Laufzeit hat, dafür aber mit Wahrscheinlichkeit kleiner 1/2 statt der richtigen Antwort keine Antwort (also ein „weiß nicht“) zurückgibt.Die beiden Definitionen sind also äquivalent. Definiert wird ZPP meist als Schnittmenge von RP und co-RP.Diejenigen Probleme, für die Las-Vegas-Algorithmen mit mittlerer polynomialer Laufzeit existieren, liegen in ZPP. ZPP wurde mit anderen probabilistischen Komplexitätsklassen 1977 von John T. Gill eingeführt.
rdf:langString
La classe ZPP, est un objet de la théorie de la complexité, en informatique théorique. C'est une classe de problèmes de décision sur machine de Turing probabiliste. L'acronyme ZPP vient de Zero-Error Probabilistic Polynomial time.
rdf:langString
In complexity theory, ZPP (zero-error probabilistic polynomial time) is the complexity class of problems for which a probabilistic Turing machine exists with these properties:
* It always returns the correct YES or NO answer.
* The running time is polynomial in expectation for every input. In other words, if the algorithm is allowed to flip a truly-random coin while it is running, it will always return the correct answer and, for a problem of size n, there is some polynomial p(n) such that the average running time will be less than p(n), even though it might occasionally be much longer. Such an algorithm is called a Las Vegas algorithm. Alternatively, ZPP can be defined as the class of problems for which a probabilistic Turing machine exists with these properties:
* It always runs in polynomial time.
* It returns an answer YES, NO or DO NOT KNOW.
* The answer is always either DO NOT KNOW or the correct answer.
* It returns DO NOT KNOW with probability at most 1/2 for every input (and the correct answer otherwise). The two definitions are equivalent. The definition of ZPP is based on probabilistic Turing machines, but, for clarity, note that other complexity classes based on them include BPP and RP. The class BQP is based on another machine with randomness: the quantum computer.
rdf:langString
Nella teoria della complessità computazionale, ZPP (Zero-error Probabilistic Polynomial time, "tempo polinomiale probabilistico con errore zero") è la classe di complessità dei problemi per i quali esiste una macchina di Turing probabilistica con queste proprietà
* Restituisce sempre la risposta corretta SÌ o NO.
* Il tempo di esecuzione è polinomiale in termini di aspettativa per ogni input. In altre parole, se l'algoritmo può lanciare una moneta veramente casuale mentre è in esecuzione, restituirà sempre la risposta corretta e, per un problema di dimensione n, c'è un qualche polinomio p(n) tale che il tempo medio di esecuzione sarà minore di p(n), anche se potrebbe essere occasionalmente molto più lungo. Tale algoritmo è chiamato . Alternativamente, ZPP può essere definita come la classe dei problemi per i quali esiste una macchina di Turing probabilistica con queste proprietà:
* Funziona sempre in tempo polinomiale.
* Restituisce una risposta SÌ, NO o NON SO.
* La risposta è sempre o NON SO o la risposta corretta.
* Restituisce NON SO con probabilità al massimo 1/2 (e la risposta corretta altrimenti). Le due definizioni sono equivalenti. La definizione di ZPP si basa sulle macchine di Turing probabilistiche, ma, per chiarezza, si noti che altre classi di complessità basate si di esse includono BPP ed RP. La classe BQP è basata su un'altra macchina dotata di casualità: il computer quantistico.
rdf:langString
계산 복잡도 이론에서 복잡도 종류 ZPP(오차 없는 확률적 다항시간, Zero-error Probabilistic Polynomial time)는 다음과 같은 성질을 지니는 확률적 튜링 기계가 존재하는 문제로 이루어진 집합이다.
* 항상 올바른 '예' 또는 '아니오' 답을 내놓는다.
* 최대 실행시간은 정해져 있지 않으나, 어떠한 입력에 대해서도 평균 다항 시간에 실행한다. 이는 문제 크기가 n이면 평균 실행 시간이 p(n)보다 작게 되는 다항식 p(n)이 존재한다는 뜻도 된다. (평균 실행 시간이 그렇다는 것이고, 각 실행은 훨씬 오래 걸릴 수 있다.) ZPP에 속한 알고리즘은 항상 올바른 답을 내놓는다. (이러한 알고리즘을 이라고 한다.) 다른 식으로 정의할 수도 있다. ZPP란 다음과 같은 성질을 지니는 확률적 튜링 기계가 존재하는 문제의 복잡도 종류이다.
* 항상 다항 시간에 실행을 마친다.
* '예', '아니오', '알 수 없음' 중 하나를 답으로 내놓는다.
* 답은 '알 수 없음'이거나 정답이어야 한다.
* 정답이 '예'라면 1/2 확률로 '예'를 답으로 내놓는다.
* 정답이 '아니오'라면 1/2 확률로 '아니오'를 답으로 내놓는다. 이 정의는 앞에서 제시한 정의와 동등하다. ZPP의 정의는 확률적 튜링 기계에 바탕을 둔다. BPP나 RP도 바탕을 같이한다. 그러나 BQP 같은 복잡도 종류는 다른 종류의 확률적 기계인 양자 컴퓨터에 바탕을 두고 있다.
rdf:langString
計算複雑性理論における ZPP とは、以下の属性をもつ確率的チューリング機械で解ける問題の複雑性クラスである。
* YES または NO の常に正しい解を返す。
* 実行時間に制限はないが、任意の入力長について平均で多項式時間かかる。 なお ZPP とは "Zero-error Probabilistic Polynomial time" の略である。 換言すれば、ZPP に属する問題を解くアルゴリズムは完全に無作為なコインを投げるとも言える。常に正しい答えを返すので、ラスベガス法に分類される。入力長 n に関する多項式 p(n) があるとき、答えを得るまでにかかる時間の平均は p(n) 未満だが、最悪の場合はもっと長くなる。 あるいは、ZPP を以下の属性を持つ確率的チューリング機械で解ける問題のクラスと定義することもできる。
* 常に多項式時間である。
* 解として YES、NO、DO NOT KNOW の三種類を返す。
* 解は DO NOT KNOW でない場合は常に正しい。
* 正解が YES である場合、YES を返す確率は最低でも 1/2 である。
* 正解が NO である場合、NO を返す確率は最低でも 1/2 である。 これら2つの定義は等価である。 ZPP の定義には確率的チューリング機械に基づいている。同様の複雑性クラスとして BPP や RP がある。クラス BQP は別のランダム性を持つ機械である量子コンピュータに基づいている。
rdf:langString
Na Teoria da complexidade computacional, ZPP (inglês: Zero-error Probabilistic Polinomial time, Probalístico de tempo polinominal sem erros) é a classe complexa de problemas em que uma Máquina de Turing existe com estas propriedades:
* Sempre retorna a resposta correta SIM ou NÃO.
* O tempo de execução é irrestrito, mas é polinominal para cada entrada. Em outras palavras, o algoritmo é como o lançamento de uma moeda honesta. Sempre retorna a resposta correta. (Tal algoritmo é chamado de algoritmo Las Vegas.) Para um problema do tamanho n , existe algum p(n) polinominal em que o tempo médio de execução será menor que p(n), ainda que este ocasionalmente demore. Podemos dizer também que, ZPP pode ser definido como a classe de problemas em que uma Máquina de Turing existe com estas propriedades:
* Sempre executa num tempo polinominal.
* Sempre retorna SIM, NÃO ou NÃO SEI.
* A resposta é sempre NÃO SEI ou a correta.
* Se a resposta e SIM, estão retorna SIM com a probabilidade de pelo menos 1/2.
* Se a resposta e NÃO, estão retorna NÃO com a probabilidade de pelo menos 1/2. A definição de ZPP é baseada na máquina probabilistica de Turing. Outros clases complexas baseadas nela incluem BPP e . A classe BQP é baseada em outra máquina aleatória: o Computador quântico.
rdf:langString
В теории вычислительной сложности ZPP (англ. zero-error probabilistic polynomial time — безошибочный вероятностный полиномиальный) — это класс задач с ответом «Да» либо «Нет», для которых существует вероятностная машина Тьюринга, удовлетворяющая следующим свойствам:
* Она всегда правильно отвечает «Да» либо «Нет».
* Математическое ожидание времени работы данной машины Тьюринга полиномиально (само время работы может быть неограниченно велико). Существует альтернативный набор свойств:
* Машина Тьюринга всегда работает за полиномиальное время.
* Она отвечает «Да», «Нет» или «Не знаю».
* Ответ может быть либо правильным, либо «Не знаю».
* Если правильный ответ «Да», машина Тьюринга отвечает «Да» с вероятностью не меньше ½.
* Если правильный ответ «Нет», машина Тьюринга отвечает «Нет» с вероятностью не меньше ½. Выбор одного из двух наборов свойств приводит к эквивалентным определениям класса ZPP. Машину Тьюринга, удовлетворяющую этим свойствам, иногда называют машиной Тьюринга типа Лас-Вегас.
rdf:langString
在計算複雜度理論內, ZPP（zero-error probabilistic polynomial time，零錯誤概率多項式時間）是一個與機率圖靈機有關的的複雜度類，並且存在以下特點：
* 這機器永遠會給出正確的"是"或者"否"的答案。
* 這個機器平均運作的時間是多項式時間以內。 換句話說，有一個演算法會在運作時使用一個完美隨機的硬幣，並且永遠回傳正確的答案（這種演算法被稱作拉斯維加斯演算法（Las Vegas algorithm））。對一個輸入大小為n的問題，存在一個多項式p(n)，令平均的運作時間小於p(n)（有可能偶爾會超過）。 另外，ZPP可以定義為一個問題的集合，裡面每個問題都存在一個可以解決此問題的機率圖靈機，且此機器性質如下：
* 運轉時間永遠是多項式時間
* 會回傳YES，NO或者DO NOT KNOW的答案
* 答案如果不是DO NOT KNOW，就會是正確的答案
* 如果問題的正確答案是YES，這機器回傳YES的機率至少是1/2（其他時候回傳DO NOT KNOW）
* 如果問題的正確答案是NO，這機器回傳NO的機率至少是1/2（其他時候回傳DO NOT KNOW） 以上這兩個定義是相等的。ZPP的定義是基於概率圖靈機。其他基於概率圖靈機的複雜度類包含了BPP和RP。至於BQP (複雜度)這個複雜度類則換成使用了量子電腦這種也是具有隨機性的電腦。
xsd:nonNegativeInteger
8930
