En muchos dominios, hay técnicas canónicas que todos los que trabajan en el campo deben dominar. Por ejemplo, para las reducciones de espacio de registro, el "truco de bits" para la composición que consiste en no construir la salida completa de la función compuesta, pero siempre solicita volver a calcular el resultado para cada bit de salida, lo que permite mantener las restricciones de espacio de registro.
Mi pregunta es sobre técnicas no relativizantes. ¿Los teóricos han esbozado algunas operaciones fundamentales no relativizantes, o hay un truco diferente para cada prueba no relativizante conocida?
cc.complexity-theory
oracles
relativization
Patey Ludovic
fuente
fuente
Respuestas:
En realidad, solo hay una técnica no relativizante "emblemática": la aritmetización (la técnica utilizada en las pruebas de IP = PSPACE, MIP = NEXP, PP⊄SIZE (n k ), MA EXP ⊄P / poly, y varios otros resultados )
Sin embargo, la prueba de que todos los lenguajes NP tienen pruebas computacionales de conocimiento cero (suponiendo que existan funciones unidireccionales), debido a Goldreich, Micali y Wigderson, utilizó una técnica diferente no relativizante (es decir, las simetrías del problema de 3 COLORES) )
Arora, Impagliazzo y Vazirani argumentaron que incluso la "capacidad de verificación local", la propiedad de los problemas NP completos utilizados en la prueba del teorema original de Cook-Levin (así como el teorema PCP), debería contar como una técnica no relativizante ( aunque Lance Fortnow escribió un artículo argumentando lo contrario). El problema es si tiene sentido relativizar la clase de complejidad de los "problemas localmente comprobables".
Los argumentos recurrentes utilizados en los resultados de la década de 1970 como TIME (n) ≠ NTIME (n) se han presentado como otro ejemplo de una técnica no relativizante.
Para obtener más información, puede consultar mi papel de algebrización con Wigderson , y especialmente las referencias allí. Tuvimos que catalogar prácticamente las técnicas no relativizantes existentes para descubrir cuáles estaban y no estaban abarcadas por la barrera de la algebrización.
Anexo: Me acabo de dar cuenta de que olvidé mencionar la computación cuántica basada en medidas (MBQC) , que Broadbent, Fitzsimons y Kashefi utilizaron recientemente con gran efecto para obtener teoremas de complejidad cuántica (como QMIP = MIP * y BQP = MIP con probadores BQP enredados y verificador BPP) que muy probablemente no se relativizan.
fuente