Demostració provable per probabilitat
En teoria de la complexitat, un sistema de demostració provable per probabilitat (o PCP per les sigles en anglès probabilistically checkable proof) és un tipus de prova que pot ser comprovada per un algorisme probabilístic usant una quantitat fitada de aleatorietat i llegint una quantitat fitada de bits de la prova. Es requereix que l'algorisme accepti les proves correctes i rebutgi les incorrectes amb una probabilitat molt alta. Una prova estàndard (o certificat), igual que el que es fa servir en la definició amb verificador de la classe NP, també satisfà aquests requeriments, ja que el procediment de comprovació de forma determinista llegeix la prova sencera, sempre accepta les proves correctes i rebutja les incorrectes.[1][2]
Aquest tipus de proves per probabilitat dona peu a diverses classes de complexitat depenent del nombre de preguntes que fan falta i la quantitat d'aleatorietat es fa servir. La classe PCP[r(n), q(n)] és la classe de complexitat del conjunt de problemes de decisió que tenen proves provable per probabilitat en temps polinòmic usant com a molt r(n) bits aleatoris llegint com a molt q(n) bits de la demostració.[1] Si no es diu el contrari, les demostracions correctes s'han d'acceptar sempre, i les incorrectes han de rebutjar-se amb una probabilitat més gran d'1/2.
Definició
[modifica]Donat un problema de decisió L (o un llenguatge L amb un alfabet Σ), una demostració provable per probabilitat per L amb una completesa c(n) i una confiança s(n), on 0 ≤ s(n) ≤ c(n) ≤ 1, consisteix en un provador i un verificador. Donada una suposada solució x amb longitud n, que pot ser falsa, el provador produeix una prova π que afirma que x resolt L (x ∈ L, la prova és una cadena ∈ Σ*). I un verificador és una màquina de Turing probabilística amb oracle V que comprova la π per la afirmació que x resolt L (o que x ∈ L) i decideix acceptar l'afirmació o no. El sistema te les següents propietats:[2]
- Completesa: per qualsevol x ∈ L, donada la prova π produïda pel productor del sistema, el verificador accepta l'afirmació amb una probabilitat com a mínim c(n)
- Robustesa: per qualsevol x ∉ L, per qualsevol prova π el verificador accepta erròniament l'afirmació amb una probabilitat com a molt s(n)
Per mesurar la complexitat computacional del verificador, es te r(n) que es la complexitat d'aleatorietat per mesurar el nombre màxim de bits que V usa en tots els x de longitud n i la complexitat de qüestió q(n) del verificador és el nombre màxim de preguntes que V fa a π sobre tots els x de longitud n.
El verificador es diu no-adaptatiu si fa totes les qüestions abans no rep totes les respostes a les qüestions anteriors.
La classe de complexitat PCPc(n), s(n)[r(n), q(n)] és la classe de complexitat de tots els problemes de decisió que tenen sistemes de prova probabilístics sobre un alfabet binari de completesa c(n) i robustesa s(n), on el verificador és no-adaptatiu, funciona en temps polinòmic i té una complexitat d'aleatorietat r(n) i de qüestió q(n).
De vegades es fa servir la notació abreviada PCP[r(n), q(n)] per escriure PCP1, ½[r(n), q(n)].
La classe de complexitat PCP es defineix com PCP1, ½[O(log n), O(1)].
Propietats
[modifica]Des del punt de vista de la complexitat computacional, per valors extrems als paràmetres, la definició de sistemes de demostració probabilístics és equivalent a certes classes de complexitat. Per exemple:[3]
- PCP[0, 0] = P. P està definida sense cap aleatorietat i cap accés a demostracions
- PCP[O(log(n)), 0] = P. Un nombre logarítmic de bits aleatoris no ajuda a una màquina de Turing de temps polinòmic, ja que pot provar totes les possibles cadenes aleatòries de longitud logarítmica en tempos polinòmic
- PCP[0,O(log(n))] = P. Sense aleatorietat, la prova es pot pensar com una cadena de mida fixa logarítmica. Una màquina de temps polinòmic pot provar totes proves de mida logarítmica en temps polinòmic.
- PCP[poly(n), 0] = coRP per la mateixa definició de la classe coRP.
- PCP[0, poly(n)] = NP per la mateixa definició basada en verificador de NP
El teorema PCP i que MIP = NEXP es pot caracteritzar com segueix:
- PCP[O(log n),O(1)] = NP (teorema PCP)[4]
- PCP[poly(n),O(1)] = PCP[poly(n),poly(n)] = NEXP (MIP = NEXP)
També se sap que PCP[r(n), q(n)] ⊆ NTIME(poly(n,2O(r(n))q(n))). En particular, PCP[log n, poly(n)] = NP.
D'altra banda, si NP ⊆ PCP[o(log n),o(log n)] llavors P = NP.[5]
PCP Lineal
[modifica]Un PCP lineal és aquell que donada una qüestió q, l'oracle només fa operacions lineals sobre la prova π. És equivalent a dir que la resposta de l'oracle a la qüestió q és una funció lineal f(q, π).
Vegeu també
[modifica]Referències
[modifica]- ↑ 1,0 1,1 Sanjeev., Arora,. Computational complexity : a modern approach. Cambridge: Cambridge University Press, 2009. ISBN 9780521424264.
- ↑ 2,0 2,1 V., Vazirani, Vijay. Approximation algorithms. Berlín: Springer, 2001. ISBN 3540653678.
- ↑ «Complexity Zoo:P - Complexity Zoo». Arxivat de l'original el 2018-01-19. [Consulta: 16 desembre 2018].
- ↑ Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario «Proof Verification and the Hardness of Approximation Problems». J. ACM, 45, 3, 5-1998, pàg. 501–555. DOI: 10.1145/278298.278306. ISSN: 0004-5411.
- ↑ Arora, Sanjeev; Safra, Shmuel «Probabilistic Checking of Proofs: A New Characterization of NP». J. ACM, 45, 1, 1-1998, pàg. 70–122. DOI: 10.1145/273865.273901. ISSN: 0004-5411.
| Considerades tractables | |
|---|---|
| Suposadament intractables | UP · NP · NP-complet · NP-hard · co-NP · co-NP-complet · AM · QMA · PH · ⊕P · PP · ♯P · ♯P-complet · IP · PSPACE · PSPACE-complet |
| Considerades intractables | |
| Jerarquia de classes | |
| Families de classes | |
