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.
| Attributes | Values |
|---|
| rdf:type
| |
| 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)
|
| 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)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| has 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)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
