Ejemplo que demuestra el poder de los circuitos no deterministas

Un circuito booleano no determinista tiene, además de las entradas ordinarias , un conjunto de entradas "no deterministas" y = ( y 1 , ... , y m ) . Un circuito no determinista C acepta la entrada x si existe y tal que la salida del circuito 1 está activada ( x , y ) . Análogo a P / p o l $x = (x_1,\dots,x_n)$$y=(y_1,\dots,y_m)$$C$$x$$y$$1$$(x,y)$$P/poly$(la clase de idiomas que se puede decidir mediante circuitos de tamaño polinómico), se puede definir como la clase de idiomas que se puede decidir mediante circuitos no deterministas de tamaño polinómico. Se cree ampliamente que los circuitos no deterministas son más potentes que los circuitos deterministas, en particular N P ⊂ P / p o l y implican que la jerarquía polinómica se colapsa.$NP/poly$$NP \subset P/poly$

¿Existe un ejemplo explícito (e incondicional) en la literatura que muestre que los circuitos no deterministas son más poderosos que los circuitos deterministas?

En particular, ¿conoce una familia de funciones computable por circuitos no deterministas de tamaño c n , pero no computable por circuitos deterministas de tamaño ( c + ϵ ) n ?$\{f_n\}_{n > 0}$$cn$$(c+\epsilon)n$

Si este problema no tiene progreso, tengo una respuesta.

-

También he considerado este problema desde mi artículo COCOON'15 (antes de su pregunta).

Ahora, tengo una estrategia de prueba, e inmediatamente, se da el teorema siguiente: Hay una función booleana tal que el determinista T 2 complejidad -Circuito de f es como máximo de 2 n + O ( n ) y el determinista T 2 -Circuito La complejidad de f es 3 n - o ( n ) .$f$$U_2$$f$$2n + o(n)$$U_2$$f$$3n - o(n)$

Pido disculpas por no haber escrito el documento. El bosquejo de prueba a continuación podría ser suficiente para explicar mi estrategia de prueba. Mi objetivo es escribir el documento con más resultados antes de la fecha límite de STACS (1 de octubre).

[Bosquejo de prueba]

Deje $f = \lor_{i=0}^{\sqrt{n}-1}{Parity_{\sqrt{n}}(x_{\sqrt{n} \cdot i + 1}, \ldots, x_{\sqrt{n} \cdot i + \sqrt{n}}})$

La prueba determinista de límite inferior se basa en un método de eliminación de puerta estándar con una pequeña modificación.

La prueba de límite superior no determinista es una construcción de dicho circuito no determinista.

1. $Parity_{\sqrt{n}}$$o(n)$
2. $\sqrt{n}$$2n + o(n)$
3. Combina los dos circuitos.