PP (complexity)
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.
Wikipage disambiguates
primaryTopic
PP (complexity)
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.
has abstract
Em Complexidade computacional, ...... o nome alternativo Majority-P
@pt
In complexity theory, PP is th ...... e alternative name Majority-P.
@en
In der Komplexitätstheorie ist ...... obabilistische Polynomialzeit.
@de
PP est un objet de la théorie ...... d'erreur inférieure à un demi.
@fr
В теории сложности, PP являетс ...... ый полиномиальный по времени».
@ru
في نظرية التعقيد الحسابي القسم ...... لتعقيد هذا عرفه غيل عام 1977 .
@ar
在計算複雜度理論內,PP是一個複雜度類,包含可以在多項式時間 ...... al time)。這個複雜度類是由Gill於1977年定義。
@zh
計算複雑性理論において、複雑性クラス PP とは、確率的チュ ...... time" を意味する。1977年、Gill が定義した。
@ja
Wikipage page ID
Wikipage revision ID
736,548,558
hypernym
type
comment
Em Complexidade computacional, ...... foi definida por Gill em 1977.
@pt
In complexity theory, PP is th ...... s was defined by Gill in 1977.
@en
In der Komplexitätstheorie ist ...... obabilistische Polynomialzeit.
@de
PP est un objet de la théorie ...... d'erreur inférieure à un demi.
@fr
В теории сложности, PP являетс ...... ый полиномиальный по времени».
@ru
في نظرية التعقيد الحسابي القسم ...... لتعقيد هذا عرفه غيل عام 1977 .
@ar
在計算複雜度理論內,PP是一個複雜度類,包含可以在多項式時間 ...... al time)。這個複雜度類是由Gill於1977年定義。
@zh
計算複雑性理論において、複雑性クラス PP とは、確率的チュ ...... time" を意味する。1977年、Gill が定義した。
@ja
label
PP (complexidade)
@pt
PP (complexity)
@en
PP (complexité)
@fr
PP (複雜度)
@zh
PP (計算複雑性理論)
@ja
Probabilistische Polynomialzeit
@de
Класс PP
@ru
بي بي (تعقيد حسابي)
@ar