Pruebas alternativas del teorema de Immerman-Szelepcsenyi

20

Immerman y Szelepcsenyi demostraron independientemente que . Usando su técnica de conteo inductivo, Borodin et al probaron que S A C i está cerrado bajo complementación, para i > 0 . Antes del teorema de Reingold ( S L = L ), Nisan y Ta-Shma demostraron S L = c o S L , utilizando reducciones de proyección uniformes en el espacio logs. Un documento de 1996 de Alvarez y Greenlaw dice "Una prueba de NNL=coNLSACii>0SL=LSL=coSLNL=conorteL usando técnicas similares a las de Nisan y Ta-Shma, aunque tal prueba sería muy interesante ". Me pregunto si tal prueba se ha encontrado en los últimos 14 años. ¿Hay alguna otra prueba alternativa? de ?norteL=ConorteL

Shiva Kintali
fuente
1
Reinhardt y Allender ofrecen un estilo de prueba muy similar, "Hacer que el no determinismo sea inequívoco" para demostrar que los gráficos de alcanzabilidad st con una ruta de longitud mínima única entre syt se pueden decidir en UL \ cap coUL.
Derrick Stolee
@Derrick: ¿podrías dar una respuesta?
András Salamon
@ András: el artículo de Reinhardt y Allender utiliza el recuento inductivo y el lema de aislamiento para mostrar que NL / poly = UL / poly, es decir, en el contexto de la complejidad no uniforme, el cálculo limitado del espacio de registro no determinista puede ser inequívoco. Este es un buen resultado relacionado, pero no merece ser agregado como respuesta.
Shiva Kintali el

Respuestas:

10

Como parece que no tenemos ninguna respuesta, ¿puedo hacer un comentario?

Supongamos que se nos dan bits, X = x 1 , , x ny tenemos que complementar cada bit para obtener ¬ x 1 , , ¬ x n . La única restricción es que el circuito que lo hace debe ser monótono. Obviamente necesitamos información adicional para hacer esto y aquí hay una de ellas.norteX=X1,,Xnorte¬X1,,¬Xnorte.

Supongamos que es el número de unidades en la entrada y de alguna manera tenemos esto como consejo. Entonces es fácil ver que ¬ x i = T h n - 1 k ( X - x i ) (es decir, en todas las entradas excepto x i ). Por supuesto, la construcción es monótona.k¬Xyo=Thknorte-1(X-Xyo)Xyo

Con esta construcción, la motivación para el conteo inductivo es clara (al menos para mí). Vale la pena preguntar qué otro consejo funcionaría. No conozco otro. Pero esto puede ser la clave de su pregunta.

V Vinay
fuente
44
O(Iniciar sesiónnorte)FFF
@Vinay, @Ramprasad: Gracias por hermosas ideas.
Shiva Kintali