Sea una clase de complejidad y sea la contraparte aleatoria de definida de la misma manera que se define con respecto a . Más formalmente, proporcionamos polinómicamente muchos bits aleatorios y aceptamos una entrada si la probabilidad de aceptar es superior a .
En una publicación anterior , pregunté si se sabía si la igualdad se mantiene entre y BP- C para C una clase de complejidad de circuito. La respuesta es sí para todas las clases de complejidad lo suficientemente expresivas como para calcular Mayoría y para AC 0 por alguna otra razón. Sin embargo, esos resultados no son uniformes y me gustaría saber:
¿Se estudian o conocen versiones uniformes de esos resultados? ¿Algún resultado parcial?
¿Implican conjeturas de larga data?
Creo que la desrandomización uniforme de es exactamente P = BPP, por lo que espero que la respuesta sea "sí", pero no tengo claro qué implicaría la desrandomización uniforme de clases pequeñas dentro de la jerarquía NC .
Respuestas:
La clase uniform-RNC ha sido estudiada mucho. Es un problema abierto si uniform-RNC = uniform-NC. Uniform- (R) NC corresponde a PRAM (aleatorizados) con polinomios procesadores y tiempo de ejecución poliligarítmico (ver el Manual de Teoría Informática Vol. A). Entonces, la pregunta es si cada algoritmo paralelo aleatorizado eficiente puede ser desrandomizado.
Dado que las pruebas de identidad simbólica determinantes se realizan en RNC uniforme, la desrandomización de RNC implica límites inferiores del circuito por los resultados de Kabanets & Impagliazzo (Complejidad computacional, 13 (1-2), páginas 1-46, 2004).
Un caso especial importante es la cuestión de si podemos calcular coincidencias perfectas en uniforme-NC. Se conocen varios algoritmos paralelos aleatorios, pero no sabemos si hay uno determinista. Recientemente, Fenner, Gurjar y Thierauf (STOC 2016) han demostrado que podemos calcular coincidencias perfectas en gráficos bipartitos mediante circuitos uniformes de profundidad poliligarítmica y tamaño cuasipolinomial.
fuente