PP (complexitat)
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.[1][2]
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.[3]
Definició
modificaUn llenguatge L és a PP si i només si existeix una màquina de Turing probabilista M tal que
- M funciona un temps polinòmic per totes les entrades
- per tot x a L, M treu 1 amb probabilitat estrictament més gran que 1/2
- per tot x no a L, M treu 0 amb probabilitat menor o igual a 1/2
Es pot definir de forma alternativa usant només màquines de Turing deterministes. Un llenguatge L és a PP si i només si existeix una màquina de Turing determinista i un polinomi p tal que
- M funciona en temps polinòmic per totes les entrades
- per tot x a L, la fracció de cadenes y de longitud p(|x|) que satisfà M(x,y) = 1 és estrictament més gran que 1/2
- per tot x no a L, la fracció de cadenes y de longitud p(|x|) que satisfà M(x,y) = 1 és menor o igual a 1/2
En ambdues definicions, es pot canviar "menor o igual a" per "menor que" i el llindar d'1/2 per qualsevol nombre racional entre (0,1) sense canviar la classe.
Relació amb d'altres classes
modificaPP conté BPP, ja que els algorismes probabilístics descrits a la definició de BPP formen una subclasse dels algorismes de la definició de PP.
PP també conte la classe NP, Això es prova veient que els problema NP-complet de satisfacibilitat (SAT) pertanyen a PP. Com que NP-complet està dins de NP, i es pot reduir qualsevol problema polinòmic a PP, NP és dins de NP. A més, com que PP és tancat respecte el complement, co-NP també és dins de PP.
Per tant, PP conté també a MA.
Es pot demostra també que PP conté la classe BQP. I es pot provar que PP és igual a la classe postBQP (BQP amb postselecció).
Per totes aquestes inclusions, PP conté QMA, que agrupa les inclusions de MA i BQP.
PP està continguda dins de PSPACE.
Referències
modifica- ↑ «Complexity Zoo:P - Complexity Zoo» (en anglès). Arxivat de l'original el 2018-01-19. [Consulta: 30 novembre 2018].
- ↑ Peter., Linz,. An introduction to formal languages and automata. 5th ed. Sudbury, MA: Jones & Bartlett Learning, 2012. ISBN 9781449615529.
- ↑ «Complexity Class of the Week: PP» (en anglès). [Consulta: 30 novembre 2018].