lo.logic – Prueba de $ DLOGTIME-CC ^ 0 = MOD [<, bit] $

Pregunta:

Sea $ CC ^ 0 [m] $ la clase de circuitos de tamaño polinómico y profundidad constante que constan enteramente de puertas $ MOD_m $ , que generan $ 1 $ sif la suma de sus entradas $ \ equiv 0 ~ (\ textrm {mod } ~ m) $ . De la misma manera que $ DLOGTIME $ -uniform $ AC ^ 0 $ es equivalente a $ FO [<, bit] = FO [+, *] $ , en múltiples fuentes 1 , 2 se afirma que $ DLOGTIME $ -uniform $ CC ^ 0 $ es equivalente a $ MOD [+, *] $ , el conjunto de oraciones lógicas que usan solo el cuantificador modular $ \ existe ^ {(m, k)} $ que se evalúa como verdadero si el número de soluciones satisfactorias es congruente con $ k $ mod $ m $ .

Sin embargo, todas las fuentes que se citan para estas afirmaciones 3 , [4], [5] solo proporcionan pruebas para las clases $ AC ^ 0, ACC ^ 0, TC ^ 0, NC ^ 1 $ y se basan en el uso de cuantificadores estándar $ \ forall, \ exist $ , que no se ha demostrado que se puedan expresar en $ CC ^ 0 $ . ¿Alguien sabe cómo modificar las pruebas originales de $ DLOGTIME-AC ^ 0 = FO [<, bit] = FO [+, *] $ para lograr $ DLOGTIME-CC ^ 0 = MOD [<, bit] = MOD [ +, *] $ sin usar estos cuantificadores, o una fuente para tales pruebas?

[4]: Introducción a la complejidad de los circuitos: un enfoque uniforme de Heribert Vollmer

[5]: Complejidad descriptiva por Neil Immerman

(Estas pruebas en su mayoría solo siguen la que se presenta en 3 )

Respuesta:

Me comuniqué con los autores de los artículos [1] y [2], y parece que ambas afirmaciones eran erróneas, lo que deja esta pregunta abierta.

Leave a Comment

Your email address will not be published.

Scroll to Top

istanbul avukat

-

web tasarım