| dbo:abstract
|
- En teoria de la complexitat, la classe de complexitat PP é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 menor de 1/2 per totes les instàncies. Si un problema de decisió és a PP, llavors hi ha un algorisme per ell que permet prendre decisions aleatòries, es garanteix que funciona durant un temps polinòmic i si la resposta és SI, l'algorisme donarà SI amb una probabilitat més gran de 1/2. Si la resposta és NO, l'algorisme respondrà SI amb una probabilitat menor de 1/2. En termes pràctics, aquesta classe és la dels problemes que poden ser resolts fins a qualsevol precisió executant un algorisme aleatori un nombre suficient de vegades. Una definició alternativa és dir que la classe PP és la que formen tots els problemes de decisió que es poden resoldre per una màquina de Turing no determinista en tempos polinòmic i que la condició d'acceptació és que la majoria de camins d'execució accepten. Per aquest motiu alguns autors suggereixen el nom Majority-P. (ca)
- في نظرية التعقيد الحسابي القسم PP هو قسم لالات تيورنج الاحتمالية التي تخطأ على كل المدخلات باحتمال . الكلمة PP هي اختصار للكلمتين probabilistic polynomial , قسم التعقيد هذا عرفه غيل عام 1977. (ar)
- In der Komplexitätstheorie ist PP die Klasse der Entscheidungen, die in von einer probabilistischen Turingmaschine in Polynomialzeit lösbar ist und die Antwort in mindestens der Hälfte der Fälle richtig ist. Die Abkürzung PP steht für Probabilistische Polynomialzeit. PP wurde durch John T. Gill eingeführt. (de)
- En teoría de la complejidad computacional PP, que quiere decir tiempo polinomial probabilístico, es una clase de problema de decisión resoluble por una máquina de Turing probabilística ( diferente de la máquina de Turing general o determinista, en que las transiciones entre estados tienen la misma probabilidad de ocurrencia) con un error de probabilidad de menos de 1/2 para todas las instancias. (es)
- In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time. The complexity class was defined by Gill in 1977. If a decision problem is in PP, then there is an algorithm for it that is allowed to flip coins and make random decisions. It is guaranteed to run in polynomial time. If the answer is YES, the algorithm will answer YES with probability more than 1/2. If the answer is NO, the algorithm will answer YES with probability less than 1/2. In more practical terms, it is the class of problems that can be solved to any fixed degree of accuracy by running a randomized, polynomial-time algorithm a sufficient (but bounded) number of times. Turing machines that are polynomially-bound and probabilistic are characterized as PPT, which stands for probabilistic polynomial-time machines. This characterization of Turing machines does not require a bounded error probability. Hence, PP is the complexity class containing all problems solvable by a PPT machine with an error probability of less than 1/2. An alternative characterization of PP is the set of problems that can be solved by a nondeterministic Turing machine in polynomial time where the acceptance condition is that a majority (more than half) of computation paths accept. Because of this some authors have suggested the alternative name Majority-P. (en)
- PP est un objet de la théorie de la complexité, un domaine de l'informatique théorique. C'est une classe de complexité probabiliste. Plus précisément c'est l'ensemble de problèmes de décision décidés par une machine de Turing probabiliste en temps polynomial avec une probabilité d'erreur inférieure à un demi. (fr)
- 計算複雑性理論において、複雑性クラス PP とは、確率的チューリング機械で多項式時間で解ける決定問題の集合であり、その際に間違う確率は常に 1/2 未満である。PP は "probabilistic polynomial time" を意味する。1977年、Gill が定義した。 (ja)
- В теории сложности, PP является классом проблем, решаемых вероятностными машинами Тьюринга за полиномиальное время, с вероятностью ошибки менее 1/2. Аббревиатура PP обозначает «вероятностный полиномиальный по времени». (ru)
- Em Complexidade computacional, PP é a classe de problemas de decisão decidíveis por uma Máquina de Turing probabilística em tempo polinomial, com uma probabilidade de erro de menos do que 1/2 para todas as instâncias. A abreviação PP se refere a tempo polinomial probabilístico. A classe de complexidade foi definida por Gill em 1977. Se um problema de decisão está em PP, então existe um algoritmo para ele que se permite "jogar moedas para cima" e tomar decisões aleatórias. É garantido que ele rode em tempo polinomial. Se a resposta é SIM, o algoritmo vai responder SIM com uma probabilidade maior do que 1/2. Se a resposta for NÃO, o algoritmo vai responder SIM com uma probabilidade menor ou igual a 1/2. Em termos mais práticos, ela é a classe dos problemas que podem ser decididos para qualquer grau de precisão fixo rodando um algoritmo de tempo polinomial aleatoriamente por um número de vezes suficientes (mas limitado). Uma caracterização alternativa para PP é o conjunto de problemas que pode ser resolvido por uma Máquina de Turing não determinística em tempo polinomial onde a condição de aceitação é que a maioria (mais da metade) dos caminhos de computação são aceitos. Por causa disso, alguns autores sugerem o nome alternativo Majority-P (pt)
- В теорії складності, PP є класом задач, розв'язуваних за поліноміальний час, з імовірністю помилки менше 1/2. Абревіатура PP позначає «імовірнісний поліноміальний за часом». (uk)
- 在計算複雜度理論內，PP是一個複雜度類，包含可以在多項式時間裡面以概率圖靈機解決，無論輸入如何錯誤率均小於1/2的決定型問題。PP這個縮寫即代表了概率多項式時間(probabilistic polynomial time)。這個複雜度類是由Gill於1977年定義。 (zh)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 15549 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- في نظرية التعقيد الحسابي القسم PP هو قسم لالات تيورنج الاحتمالية التي تخطأ على كل المدخلات باحتمال . الكلمة PP هي اختصار للكلمتين probabilistic polynomial , قسم التعقيد هذا عرفه غيل عام 1977. (ar)
- In der Komplexitätstheorie ist PP die Klasse der Entscheidungen, die in von einer probabilistischen Turingmaschine in Polynomialzeit lösbar ist und die Antwort in mindestens der Hälfte der Fälle richtig ist. Die Abkürzung PP steht für Probabilistische Polynomialzeit. PP wurde durch John T. Gill eingeführt. (de)
- En teoría de la complejidad computacional PP, que quiere decir tiempo polinomial probabilístico, es una clase de problema de decisión resoluble por una máquina de Turing probabilística ( diferente de la máquina de Turing general o determinista, en que las transiciones entre estados tienen la misma probabilidad de ocurrencia) con un error de probabilidad de menos de 1/2 para todas las instancias. (es)
- PP est un objet de la théorie de la complexité, un domaine de l'informatique théorique. C'est une classe de complexité probabiliste. Plus précisément c'est l'ensemble de problèmes de décision décidés par une machine de Turing probabiliste en temps polynomial avec une probabilité d'erreur inférieure à un demi. (fr)
- 計算複雑性理論において、複雑性クラス PP とは、確率的チューリング機械で多項式時間で解ける決定問題の集合であり、その際に間違う確率は常に 1/2 未満である。PP は "probabilistic polynomial time" を意味する。1977年、Gill が定義した。 (ja)
- В теории сложности, PP является классом проблем, решаемых вероятностными машинами Тьюринга за полиномиальное время, с вероятностью ошибки менее 1/2. Аббревиатура PP обозначает «вероятностный полиномиальный по времени». (ru)
- В теорії складності, PP є класом задач, розв'язуваних за поліноміальний час, з імовірністю помилки менше 1/2. Абревіатура PP позначає «імовірнісний поліноміальний за часом». (uk)
- 在計算複雜度理論內，PP是一個複雜度類，包含可以在多項式時間裡面以概率圖靈機解決，無論輸入如何錯誤率均小於1/2的決定型問題。PP這個縮寫即代表了概率多項式時間(probabilistic polynomial time)。這個複雜度類是由Gill於1977年定義。 (zh)
- En teoria de la complexitat, la classe de complexitat PP é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 menor de 1/2 per totes les instàncies. Una definició alternativa és dir que la classe PP és la que formen tots els problemes de decisió que es poden resoldre per una màquina de Turing no determinista en tempos polinòmic i que la condició d'acceptació és que la majoria de camins d'execució accepten. Per aquest motiu alguns autors suggereixen el nom Majority-P. (ca)
- In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time. The complexity class was defined by Gill in 1977. (en)
- Em Complexidade computacional, PP é a classe de problemas de decisão decidíveis por uma Máquina de Turing probabilística em tempo polinomial, com uma probabilidade de erro de menos do que 1/2 para todas as instâncias. A abreviação PP se refere a tempo polinomial probabilístico. A classe de complexidade foi definida por Gill em 1977. (pt)
|
| rdfs:label
|
- بي بي (تعقيد حسابي) (ar)
- PP (complexitat) (ca)
- Probabilistische Polynomialzeit (de)
- PP (clase de complejidad) (es)
- PP (complexité) (fr)
- PP (計算複雑性理論) (ja)
- PP (complexity) (en)
- PP (complexidade) (pt)
- Класс PP (ru)
- Клас складності PP (uk)
- PP (複雜度) (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 | |
