| dbo:abstract
|
- En teoria de la complexitat, la classe de complexitat BPP (bounded-error probabilistic polynomial time) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing probabilística en un temps polinòmic amb un error fitat de 1/2 per totes les instàncies. BPP és la classe més gran amb problemes pràctics, ja que molts problemes d'interès a BPP tenen algorismes probabilístics que poden ser executats en màquines modernes. BPP conté P, ja que una màquina determinista és un cas especial de màquina probabilística. Informalment, un problema és a BPP si hi ha un algorisme amb les següents propietats:
* pot prendre decisions aleatòries
* es garanteix que s'executa amb temps polinòmic
* a cada execució de l'algorisme, hi ha una probabilitat de com a molt 1/3 de donar la resposta incorrecta, ja sigui SI o NO. (ca)
- V teorii složitosti je BPP 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 pravděpodobnost správné odpovědi je větší než ½ a je možno ji od ½ odrazit konstantou. BPP je obvykle považována za největší třídu problémů, které jsou efektivně řešitelné (menší třídy považované za efektivně řešitelné jsou P a RP), přesto lze v této třídě nalézt i efektivně neřešitelné problémy (se složitostí například N1000000). (cs)
- في علم التعقيد الحسابي قسم التعقيد BPP هو قسم المسائل التي يوجد آلة تيورنج احتمالية وقتها كثير حدود بحيث أن احتمال الخطأ على الأكثر 1/3 لكل المُدخلات. إذا اخترنا أي عدد اقل من 1/2 حينها القسم BPP لا يتغير وذلك بطريقة استخدام الخوارزمية عدة مرات . (ar)
- In computational complexity theory, a branch of computer science, bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded by 1/3 for all instances.BPP is one of the largest practical classes of problems, meaning most problems of interest in BPP have efficient probabilistic algorithms that can be run quickly on real modern machines. BPP also contains P, the class of problems solvable in polynomial time with a deterministic machine, since a deterministic machine is a special case of a probabilistic machine. Informally, a problem is in BPP if there is an algorithm for it that has the following properties:
* It is allowed to flip coins and make random decisions
* It is guaranteed to run in polynomial time
* On any given run of the algorithm, it has a probability of at most 1/3 of giving the wrong answer, whether the answer is YES or NO. (en)
- In der Komplexitätstheorie steht BPP (englische Abkürzung für bounded error probabilistic polynomial time) für eine Komplexitätsklasse von Entscheidungsproblemen. Ein Problem liegt in BPP, wenn es einen polynomiell zeitbeschränkten probabilistischen Algorithmus gibt, der das Problem löst und dessen Fehlerwahrscheinlichkeit höchstens 1/3 beträgt. Die Verwendung einer beliebigen anderen konstanten Fehlerschranke kleiner als 1/2 ändert nichts an der Definition der Klasse BPP, durch mehrmalige Anwendung eines gegebenen BPP-Algorithmus lässt sich jede beliebige Fehlerschranke erreichen. BPP-Algorithmen sind Monte-Carlo-Algorithmen, da sie mit einer geringen Wahrscheinlichkeit ein falsches Ergebnis liefern. Sie wurde 1977 mit anderen probabilistischen Komplexitätsklassen von John T. Gill eingeführt. (de)
- En , BPP estas la de solveblaj per probableca maŝino de Turing en polinoma tempo kun erar-probablo de maksimume 1/3 por ĉiuj okazoj. La mallongigo BPP estas de Barita, Probableca, Polinomia tempo. Se problemo estas en BPP, tiam estas algoritmo por ĝi, al kiu estas permesite klaki monerojn kaj fari hazardaj decidojn. Ĝi estas garantiita al ruliĝi en polinoma tempo. Sur iu ajn donita kuro de la algoritmo, ĝi redonas eraran respondo kun probableco ne pli granda ol 1/3, por ambaŭ okazoj de la vera respondo estas "jes" aŭ "ne". La elekto de 1/3 en la difino estas ajna. Ĝi povas esti iu ajn konstanto inter 0 kaj 1/2 malinkluzivite de "1/2" kaj la aro BPP restas neŝanĝita; tamen, tiu konstanto devas esti sendependa de la enigo. La ideo estas, ke estas probablo de eraro, sed se la algoritmo estas kurita multajn fojojn, la ŝanco, ke la plejparto de la kuroj estas eraraj sekve de la . Ĉi tio ebligas krei alte precizan algoritmon nur per kuro de la algoritmo kelkfoje kaj preno de la plejparta rezulto kiel la respondo. BPP estas unu el la plej grandaj praktikaj klasoj de problemoj, kio signifas, ke plej problemoj de intereso en BPP havas kompetentajn probablecajn algoritmojn, kiuj povas esti kuritaj rapide sur realaj modernaj maŝinoj, per la maniero priskribita pli supre. Pro ĉi tiu kaŭzo estas de granda praktika intereso kiuj problemoj kaj klasoj de problemoj estas en BPP. (eo)
- En informatique théorique, plus précisément en théorie de la complexité, la classe BPP (bounded-error probabilistic polynomial time) est la classe de problèmes de décision décidés par une machine de Turing probabiliste en temps polynomial, avec une probabilité d'erreur dans la réponse inférieure à 1/3. (fr)
- 유계오차 확률적 다항시간(有界誤差 確率的 多項時間), BPP(Bounded-error, Probabilistic, Polynomial time)는 계산 복잡도 이론에서 확률적 튜링 기계로 모든 문제에 대해서 최대 1/3의 오류가 발생하면서 다항시간에 풀 수 있는 판정 문제의 집합이다. 어떤 문제가 BPP에 속하면, 내부적으로 동전을 던져서 무작위로 진행방향을 결정하여 이 문제를 풀 수 있는 알고리즘이 존재하고 이 알고리즘은 다항시간안에 실행된다. 이 알고리즘을 실행할 때, 잘못된 실행결과를 내놓을 확률은 최대 1/3이다. 여기서 잘못된 실행결과는 '예'나 '아니오'라는 대답을 내놓는 모든 경우에 해당한다. 여기서 1/3이라는 확률이 특수한 의미를 가지는 것은 아니다. 1/3 대신 입력값에 따라 달라지지 않는 0과 1/2 사이의 적당한 확률을 지정해서 정의해도 BPP의 집합은 변하지 않는다. (ko)
- 計算複雑性理論においてBPPとは、確率的チューリングマシンによって、誤り確率が高々1/3で多項式時間で解ける決定問題の複雑性クラスである。Bounded-error Probabilistic Polynomial timeの頭文字をとったものである。ある問題がBPPに属するなら、コイントスなどによるランダムな決定を許す多項式時間で実行可能なアルゴリズムが存在する。そのアルゴリズムは、解がYESのときもNOのときも最大で1/3の確率で間違った答えを返す。 定義の1/3というのは、0以上1/2未満の間の入力と独立な定数で任意である。そして、その定数が変化しても、BPPは変化しない。これは、そのアルゴリズムを複数回実行したとき、解の多数派が誤りであることが指数関数的に減少することによる。この性質は複数回アルゴリズムを実行し、解の多数決をとることにより、高い精度のアルゴリズムを作る事を可能にする。 (ja)
- Nella teoria della complessità computazionale, BPP (Bounded-error Probabilistic Polynomial time, "tempo polinomiale probabilistico con errore limitato") è una classe di complessità a cui appartengono quei problemi decisionali che richiedono un tempo polinomiale per avere una soluzione probabilistica corretta. Più precisamente, essi sono risolvibili in tempo polinomiale da una macchina di Turing probabilistica, con una probabilità di errore al massimo di 1/3 per tutte le istanze. Informalmente, un problema è in BPP se c'è un algoritmo per esso che ha le seguenti proprietà:
* È consentito lanciare monete e prendere decisioni casuali
* È garantito che sia eseguito in tempo polinomiale
* In qualsiasi data esecuzione dell'algoritmo, esso ha una probabilità al più pari a 1/3 di dare la risposta sbagliata, sia che la risposta sia SÌ oppure NO. (it)
- В теории алгоритмов классом сложности BPP (от англ. bounded-error, probabilistic, polynomial) называется класс предикатов, быстро (за полиномиальное время) вычислимых и дающих ответ с высокой вероятностью (причём, жертвуя временем, можно добиться сколь угодно высокой точности ответа). Задачи, решаемые вероятностными методами и лежащие в BPP, возникают на практике очень часто. (ru)
- Na teoria da complexidade computacional, BPP (inglês: Bounded-error Probabilistic Polinomial time, probabilístico de tempo polinomial comprometido à erros) é a classe de solúveis por uma Máquina de Turing em tempo polinomial, com uma probabilidade de erro de no máximo 1/3 para todas as instâncias. Informalmente, um problema está em BPP se existe um algoritmo para ele que tenha as seguintes propriedades:
* É permitido "jogar moedas" e fazer decisões aleatórias
* É garantido que será executado em tempo polinomial
* Em qualquer dada execução do algoritmo, o mesmo tem a probabilidade de no máximo 1/3 de fornecer uma resposta errada, se a resposta for SIM ou NÃO. (pt)
- 在計算複雜度理論裡面，BPP是在多項式時間內以機率圖靈機解出的問題的集合, 並且對所有的輸入，輸出結果有錯誤的概率在1/3之內。BPP這個簡寫代表"Bounded-error"(有限錯誤)，"Probabilistic"(機率的)，"Polynomial time"(多項式時間)。 要是一個問題在BPP集合裡面，則存在一個演算法，此演算法允許轉硬幣作隨機的決定，並在多項式時間內結束。 對這個演算法的任何輸入，他都要在小於1/3的錯誤概率之下給出正確判斷，不論這一個問題的答案是"正確"或者"錯誤"。 在這裡定義裡面的1/3是任意給定的。它可以是在 0 與 1/2(不包含0與1/2自身) 之間的 任意常數而BPP集合維持不變(當然這個常數必須跟輸入值為何無關)。原因在於，雖然這演算法有錯誤的機率，但是只要我們多進行幾次演算法，那多數的答案都是錯誤的機率會呈現指數衰減 [1]（页面存档备份，存于互联网档案馆）. 因此證明我們可以很簡單的架構一個更準確的演算法，僅僅單純多重複幾次這個演算法然後對每次的答案作多數決。 BPP是大小最大的幾個實際的問題類別之一，代表大多數的BPP問題都有有效率的概率演算法，因此以上倏地方法可以用現在的機器快速取得解答。因為這個原因，我們對哪一些問題或問題種類在BPP裡面有著實用方面的興趣。 (zh)
- В теорії алгоритмів класом складності BPP (від англ. bounded-error, probabilistic, polynomial) називається клас предикатів, які швидко (за поліноміальний час) обчислюються і дають відповідь з високою вірогідністю (причому, жертвуючи часом, можна домогтися як завгодно високої точності відповіді). Задачі, які розв'язуються ймовірнісними методами і лежать в BPP, виникають на практиці дуже часто. (uk)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 18496 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:date
| |
| dbp:url
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- V teorii složitosti je BPP 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 pravděpodobnost správné odpovědi je větší než ½ a je možno ji od ½ odrazit konstantou. BPP je obvykle považována za největší třídu problémů, které jsou efektivně řešitelné (menší třídy považované za efektivně řešitelné jsou P a RP), přesto lze v této třídě nalézt i efektivně neřešitelné problémy (se složitostí například N1000000). (cs)
- في علم التعقيد الحسابي قسم التعقيد BPP هو قسم المسائل التي يوجد آلة تيورنج احتمالية وقتها كثير حدود بحيث أن احتمال الخطأ على الأكثر 1/3 لكل المُدخلات. إذا اخترنا أي عدد اقل من 1/2 حينها القسم BPP لا يتغير وذلك بطريقة استخدام الخوارزمية عدة مرات . (ar)
- En informatique théorique, plus précisément en théorie de la complexité, la classe BPP (bounded-error probabilistic polynomial time) est la classe de problèmes de décision décidés par une machine de Turing probabiliste en temps polynomial, avec une probabilité d'erreur dans la réponse inférieure à 1/3. (fr)
- 유계오차 확률적 다항시간(有界誤差 確率的 多項時間), BPP(Bounded-error, Probabilistic, Polynomial time)는 계산 복잡도 이론에서 확률적 튜링 기계로 모든 문제에 대해서 최대 1/3의 오류가 발생하면서 다항시간에 풀 수 있는 판정 문제의 집합이다. 어떤 문제가 BPP에 속하면, 내부적으로 동전을 던져서 무작위로 진행방향을 결정하여 이 문제를 풀 수 있는 알고리즘이 존재하고 이 알고리즘은 다항시간안에 실행된다. 이 알고리즘을 실행할 때, 잘못된 실행결과를 내놓을 확률은 최대 1/3이다. 여기서 잘못된 실행결과는 '예'나 '아니오'라는 대답을 내놓는 모든 경우에 해당한다. 여기서 1/3이라는 확률이 특수한 의미를 가지는 것은 아니다. 1/3 대신 입력값에 따라 달라지지 않는 0과 1/2 사이의 적당한 확률을 지정해서 정의해도 BPP의 집합은 변하지 않는다. (ko)
- 計算複雑性理論においてBPPとは、確率的チューリングマシンによって、誤り確率が高々1/3で多項式時間で解ける決定問題の複雑性クラスである。Bounded-error Probabilistic Polynomial timeの頭文字をとったものである。ある問題がBPPに属するなら、コイントスなどによるランダムな決定を許す多項式時間で実行可能なアルゴリズムが存在する。そのアルゴリズムは、解がYESのときもNOのときも最大で1/3の確率で間違った答えを返す。 定義の1/3というのは、0以上1/2未満の間の入力と独立な定数で任意である。そして、その定数が変化しても、BPPは変化しない。これは、そのアルゴリズムを複数回実行したとき、解の多数派が誤りであることが指数関数的に減少することによる。この性質は複数回アルゴリズムを実行し、解の多数決をとることにより、高い精度のアルゴリズムを作る事を可能にする。 (ja)
- В теории алгоритмов классом сложности BPP (от англ. bounded-error, probabilistic, polynomial) называется класс предикатов, быстро (за полиномиальное время) вычислимых и дающих ответ с высокой вероятностью (причём, жертвуя временем, можно добиться сколь угодно высокой точности ответа). Задачи, решаемые вероятностными методами и лежащие в BPP, возникают на практике очень часто. (ru)
- 在計算複雜度理論裡面，BPP是在多項式時間內以機率圖靈機解出的問題的集合, 並且對所有的輸入，輸出結果有錯誤的概率在1/3之內。BPP這個簡寫代表"Bounded-error"(有限錯誤)，"Probabilistic"(機率的)，"Polynomial time"(多項式時間)。 要是一個問題在BPP集合裡面，則存在一個演算法，此演算法允許轉硬幣作隨機的決定，並在多項式時間內結束。 對這個演算法的任何輸入，他都要在小於1/3的錯誤概率之下給出正確判斷，不論這一個問題的答案是"正確"或者"錯誤"。 在這裡定義裡面的1/3是任意給定的。它可以是在 0 與 1/2(不包含0與1/2自身) 之間的 任意常數而BPP集合維持不變(當然這個常數必須跟輸入值為何無關)。原因在於，雖然這演算法有錯誤的機率，但是只要我們多進行幾次演算法，那多數的答案都是錯誤的機率會呈現指數衰減 [1]（页面存档备份，存于互联网档案馆）. 因此證明我們可以很簡單的架構一個更準確的演算法，僅僅單純多重複幾次這個演算法然後對每次的答案作多數決。 BPP是大小最大的幾個實際的問題類別之一，代表大多數的BPP問題都有有效率的概率演算法，因此以上倏地方法可以用現在的機器快速取得解答。因為這個原因，我們對哪一些問題或問題種類在BPP裡面有著實用方面的興趣。 (zh)
- В теорії алгоритмів класом складності BPP (від англ. bounded-error, probabilistic, polynomial) називається клас предикатів, які швидко (за поліноміальний час) обчислюються і дають відповідь з високою вірогідністю (причому, жертвуючи часом, можна домогтися як завгодно високої точності відповіді). Задачі, які розв'язуються ймовірнісними методами і лежать в BPP, виникають на практиці дуже часто. (uk)
- En teoria de la complexitat, la classe de complexitat BPP (bounded-error probabilistic polynomial time) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing probabilística en un temps polinòmic amb un error fitat de 1/2 per totes les instàncies. BPP és la classe més gran amb problemes pràctics, ja que molts problemes d'interès a BPP tenen algorismes probabilístics que poden ser executats en màquines modernes. BPP conté P, ja que una màquina determinista és un cas especial de màquina probabilística. (ca)
- In der Komplexitätstheorie steht BPP (englische Abkürzung für bounded error probabilistic polynomial time) für eine Komplexitätsklasse von Entscheidungsproblemen. Ein Problem liegt in BPP, wenn es einen polynomiell zeitbeschränkten probabilistischen Algorithmus gibt, der das Problem löst und dessen Fehlerwahrscheinlichkeit höchstens 1/3 beträgt. Die Verwendung einer beliebigen anderen konstanten Fehlerschranke kleiner als 1/2 ändert nichts an der Definition der Klasse BPP, durch mehrmalige Anwendung eines gegebenen BPP-Algorithmus lässt sich jede beliebige Fehlerschranke erreichen. (de)
- In computational complexity theory, a branch of computer science, bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded by 1/3 for all instances.BPP is one of the largest practical classes of problems, meaning most problems of interest in BPP have efficient probabilistic algorithms that can be run quickly on real modern machines. BPP also contains P, the class of problems solvable in polynomial time with a deterministic machine, since a deterministic machine is a special case of a probabilistic machine. (en)
- En , BPP estas la de solveblaj per probableca maŝino de Turing en polinoma tempo kun erar-probablo de maksimume 1/3 por ĉiuj okazoj. La mallongigo BPP estas de Barita, Probableca, Polinomia tempo. Se problemo estas en BPP, tiam estas algoritmo por ĝi, al kiu estas permesite klaki monerojn kaj fari hazardaj decidojn. Ĝi estas garantiita al ruliĝi en polinoma tempo. Sur iu ajn donita kuro de la algoritmo, ĝi redonas eraran respondo kun probableco ne pli granda ol 1/3, por ambaŭ okazoj de la vera respondo estas "jes" aŭ "ne". (eo)
- Nella teoria della complessità computazionale, BPP (Bounded-error Probabilistic Polynomial time, "tempo polinomiale probabilistico con errore limitato") è una classe di complessità a cui appartengono quei problemi decisionali che richiedono un tempo polinomiale per avere una soluzione probabilistica corretta. Più precisamente, essi sono risolvibili in tempo polinomiale da una macchina di Turing probabilistica, con una probabilità di errore al massimo di 1/3 per tutte le istanze. Informalmente, un problema è in BPP se c'è un algoritmo per esso che ha le seguenti proprietà: (it)
- Na teoria da complexidade computacional, BPP (inglês: Bounded-error Probabilistic Polinomial time, probabilístico de tempo polinomial comprometido à erros) é a classe de solúveis por uma Máquina de Turing em tempo polinomial, com uma probabilidade de erro de no máximo 1/3 para todas as instâncias. Informalmente, um problema está em BPP se existe um algoritmo para ele que tenha as seguintes propriedades: (pt)
|
| rdfs:label
|
- BPP (ar)
- BPP (complexitat) (ca)
- BPP (třída složitosti) (cs)
- BPP (Komplexitätsklasse) (de)
- BPP (komplikeco) (eo)
- BPP (complexity) (en)
- BPP (complessità) (it)
- BPP (complexité) (fr)
- 유계오차 확률적 다항시간 (ko)
- BPP (計算複雑性理論) (ja)
- BPP (pt)
- Класс BPP (ru)
- Клас складності BPP (uk)
- BPP (複雜度) (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
