Teorema de PCP y complejidad de la prueba?

8

Se sabe que si P=NP entonces CoNP=PCP[O(log(n)),O(1)] . Además, se sabe que NEXP=PCP[poly(n),poly(n)]. Parece que el PCP no puede decirnos qué problemas naturales no están en NP . Me pregunto si es posible utilizar la caracterización PCP a separada CoNP de NP .

¿Cuáles son los mejores límites en la complejidad de aleatoriedad r(n) y la complejidad de consulta q(n) modo que el problema de tautología esté en PCP[O(r(n)),O(q(n))] ?

Mohammad Al-Turkistany
fuente
66
Se sabe que NEXP = PCP [poli (n), O (1)] como consecuencia del teorema de PCP. Véase, por ejemplo, la introducción del artículo de Or Meir en FOCS 2009: wisdom.weizmann.ac.il/~orm/papers/efficient_pcps_overview.pdf
Tsuyoshi Ito
1
Usted menciona la complejidad de la prueba en el título (y las etiquetas originales). ¿La complejidad computacional del problema de la tautología está relacionada con la complejidad de la prueba?
Tsuyoshi Ito
Sí, si P = CoNP, entonces las tautologías tendrían pruebas cortas.
Mohammad Al-Turkistany
@Ito, la complejidad de la prueba generalmente estudia los sistemas de prueba que establecen tautologías proposicionales. Cualquier sistema de prueba puede considerarse como un algoritmo no determinista para el problema de la tautología. La complejidad de la prueba, entonces, es el estudio de algoritmos no deterministas para el problema de la tautología.
Iddo Tzameret
@turkistany, te referías a NP = coNP.
Iddo Tzameret

Respuestas:

12

No se conocen resultados como . Desafortunadamente, separar N P y c o N P no es una fruta que cuelgue bajo ...coNPPCP[o(n),q]NPcoNP

Dana Moshkovitz
fuente
En realidad, creo que podría ser afortunado en lugar de desafortunado. Si fuera tan simple separarlos, entonces toda la comunidad se vería bastante tonta por no haberlo visto antes.
Joe Fitzsimons
44
coNPNP2no(1)2o(n)PCP[no(1),poly(n)]
1
@Boaz, esta es una buena respuesta. ¿Podrías moverlo y convertirlo en una respuesta separada?
Mohammad Al-Turkistany
12

Creo que el siguiente documento ayudará: Las pruebas interactivas de ronda de pollogarítmicos para coNP colapsan la jerarquía exponencial

coNPIP[logO(1)n]IP[k]k

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 .

MS Dousti
fuente
¿Podría por favor explicar la relevancia del segundo artículo?
Iddo Tzameret
Aquí se presenta una introducción informal al segundo documento . La frase "Todos los sistemas de prueba conocidos (incluso los probadores múltiples) para co-NP requieren probadores con complejidad #P" es el corazón de lo que se relaciona con la discusión actual.
MS Dousti