Límites inferiores para el tamaño de los circuitos no deterministas

Se sabe que el tamaño mínimo de los U_2 que calculan la función de paridad es exactamente igual a . La prueba de límite inferior se basa en el método de eliminación de puerta.$U_2$$3(n-1)$

Recientemente, noté que el método de eliminación de compuerta funciona bien también para U_2 no deterministas , y podemos probar un límite inferior para el tamaño de los U_2 no deterministas que calculan la función de paridad.$U_2$$3(n-1)$$U_2$

(Significa que el cálculo no determinista es inútil para calcular la paridad por los U_2 y no puede reducir el tamaño de . Por lo tanto, los circuitos mínimos no cambian desde el caso determinista).$U_2$$3(n-1)$

Mis preguntas son las siguientes dos:

(1) ¿Es este un nuevo resultado o un resultado conocido?

(2) En términos más generales, ¿existen algunos resultados conocidos de límites inferiores para el tamaño de los circuitos no deterministas (incluidas fórmulas, circuitos de profundidad constante, etc.) con bits de entrada no deterministas ilimitados (o, en otras palabras, no determinismo ilimitado) para un explícito ¿función?

Explicación adicional (27 de noviembre de 2014)

En la segunda pregunta, tenía la intención de saber especialmente si este es el primer límite inferior no trivial para el tamaño de los circuitos no deterministas (incluidas fórmulas, circuitos de profundidad constante, etc.) con no determinismo ilimitado para una función explícita o no. Sé que hay algunos resultados si el no determinismo es limitado, como sigue.

[1] Hartmut Klauck: límites más bajos para la computación con no determinismo limitado. IEEE Conference on Computational Complexity 1998: 141-

[2] Vikraman Arvind, KV Subrahmanyam, NV Vinodchandran: La complejidad de la consulta de verificación de programas por circuitos de profundidad constante. ISAAC 1999: 123-132

Una respuesta parcial a la segunda pregunta:

• los límites inferiores exponenciales para funciones explícitas para cualquier clase que contenga 3-CNF no se traducen en límites inferiores exponenciales para el no determinismo ilimitado, porque uno puede transformar cualquier circuito de tamaño en un 3-CNF no determinista de tamaño con no determinismo ,$S$$O(S)$$S$
• incluso si desea que el no determinismo sea inferior a S, esto todavía es factible si la función se calcula mediante una fórmula (por ejemplo, paridad), porque uno puede dividir esta fórmula de tamaño en, digamos, piezas que introducen nuevas variables, y la fórmula resultante será el tamaño (aunque la constante en el$B_2$$S$$S/100$$S/100$$O(S)$ será grande),$O()$
• para el no determinismo limitado (pero creciente), uno puede, por supuesto, usar buenos límites antiguos (por ejemplo, el límite inferior exponencial de Hastad para la paridad sigue siendo exponencial si el no determinismo es mucho menor que n 1 / d : simplemente enumere todos los posibles bits para el no determinismo y tomar un gran OR de las fórmulas resultantes).$2^{n^{1/d}}$$n^{1/d}$

Una respuesta parcial a la primera pregunta:

• no conocido para mí :) sería interesante ver la prueba (en particular, ¿cómo se pueden sustituir los valores por las variables existenciales).