Se sabe que si entonces . Además, se sabe que . Parece que el PCP no puede decirnos qué problemas naturales no están en . Me pregunto si es posible utilizar la caracterización PCP a separada de .
¿Cuáles son los mejores límites en la complejidad de aleatoriedad y la complejidad de consulta modo que el problema de tautología esté en ?
cc.complexity-theory
pcp
proof-complexity
Mohammad Al-Turkistany
fuente
fuente
Respuestas:
No se conocen resultados como . Desafortunadamente, separar N P y c o N P no es una fruta que cuelgue bajo ...c o NPAGS⊈ PCPAGS[ o ( n ) , q] nortePAGS c o NPAGS
fuente
Creo que el siguiente documento ayudará: Las pruebas interactivas de ronda de pollogarítmicos para coNP colapsan la jerarquía exponencial
Con respecto a la relación natural entre pruebas interactivas y comprobables probabilísticamente, creo que el resultado anterior debe ayudar.
También sugiero echar un vistazo a Un nuevo protocolo de muestreo y aplicaciones para basar primitivas criptográficas en la dureza de NP .
fuente